首页 > 试题广场 >

剪花布条

[编程题]剪花布条
  • 热度指数：1993 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入描述:
输入包含多组数据。

每组数据包含两个字符串s,t，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。


输出描述:
对应每组输入，输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就输出0，每个结果占一行。
示例1

输入

abcde a3
aaaaaa aa

输出

0
3
算法知识视频讲解
添加回答
Java
ZZZYZQ头像 ZZZYZQ 
//贪心算法
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()) {
            String s = in.next();
            String t = in.next();
            int ans = cut(s,t);
            System.out.println(ans);
        }
    }
    
    public static int cut(String s, String t) {
        int indexS = s.indexOf(t);
        if(indexS == -1) {
            return 0;
        }
        return 1 + cut(s.substring(indexS + t.length()),t);
    }
}

发表于 2021-08-02 23:52:24 回复(0)
C/C++
Cavs头像 Cavs 
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

#define INF 1000000
using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);

	string s, t;
	while (cin >> s >> t)
	{
		int res = 0;
		size_t pos = 0;
		while ((pos = s.find(t,pos)) != string::npos)
		{
			pos += t.size();
			++res;
		}

		cout << res << endl;
	}

	return 0;
}

发表于 2017-07-12 19:40:04 回复(2)
新世纪的神头像 新世纪的神 
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1005;
int Next[maxn];
int n,m;
char s[maxn],t[maxn];
void init(int num){
    Next[0]=-1;
    Next[1]=0;
    int pos=2,cn=0;
    while(pos<m){
        if(t[pos-1]==s[cn]){
            Next[pos++]=++cn;
        }
        else if(cn>0){
            cn=Next[cn];
        }
        else{
            Next[pos++]=0;
        }
    }
}
void print(int num){
    for(int i=0;i<num;i++){
        printf("%d ",Next[i]);
    }
    printf("\n");
}
void solve(){
    int ans=0;
   	int i=0,j=0;
    while(i<n){
        if(s[i]==t[j]){
            i++;
            j++;
            if(j==m){
             	j=0;
                ans++;
            }
        }
        else if(Next[j]>-1){
            j=Next[j];
        }
        else{
            i++;
        }
    }
    printf("%d\n",ans);
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%s%s",s,t)>0){
        n=strlen(s),m=strlen(t);
        init(m);
        //print(m);
        solve();
    }
    return 0;
}
kmp算法
发表于 2016-08-14 13:14:33 回复(0)
牛客721222号头像 牛客721222号
按道理来说，就是字符串匹配，我写了个KMP算法。 
#include <iostream>
#include <string>
using namespace std;


string s;
string t;
int nxt[1005];

void cal_next() {
	nxt[0] = -1;
	int n = t.size();
	int i=1,j=0;
	while (i < n) {
		if (j == -1 || t[i] == t[j]) {
			j++;
			i++;
			if (t[i] == t[j]) {
				nxt[i] = nxt[j];
			}
			else {
				nxt[i] = j;
			}
		}
		else {
			j = nxt[j];
		}
	}
}

int main() {
	int i, j;
	while (cin >> s >> t) {
		int count = 0;
		cal_next();
		int i, j;
		int n = s.size();
		int m = t.size();
		i = j = 0;
		while (i < n) {
			if (j== -1 || s[i] == t[j]) {
				i++;
				j++;
				if (j == m) {
					j = 0;
					count++;
				}
			}
			else {
				j = nxt[j];
			}
		}
		cout << count << endl;
	
	}


	return 0;
}
编辑于 2016-07-07 17:14:58 回复(0)
Python
华科平凡头像 华科平凡

python solution:

import sys
for i in sys.stdin.readlines():
    a,b=i.strip().split()
    print(a.count(b))
发表于 2017-11-16 18:17:23 回复(0)
kestars头像 kestars 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            String s=scanner.next();
            String t=scanner.next();
            int count=0;
            while(s.contains(t)){
                s=s.replaceFirst(t,"");
                count++;
            }
            System.out.println(count);
        }
    }
}

发表于 2018-09-20 19:35:44 回复(1)
C/C++
WZ_Dale头像 WZ_Dale 
#include <iostream>
#include <string>

using namespace std;

int main(){
    string str, s;
    int count = 0;
    while(cin >> str >> s){
        count = 0;
        size_t pos = 0;
        //while((pos = str.find(s)) != string::npos){
        //    str.erase(pos, pos + s.size());
        //    ++count;
        //}
        while((pos = str.find(s, pos)) != string::npos){
            pos += s.size();
            ++count;
        }
        cout << count << endl;
    }
    return 0;
}

编辑于 2020-08-20 11:52:50 回复(0)
Java
F2999头像 F2999 
        import java.util.Scanner;

        // 注意类名必须为 Main, 不要有任何 package xxx 信息

        public class Main {

            public static void main(String[] args) {

                Scanner in = new Scanner(System.in);

                // 注意 hasNext 和 hasNextLine 的区别

                while (in.hasNext()) { // 注意 while 处理多个 case

                    String cotton = in.next();

                    String small = in.next();

                    int count = 0;

                    for (int i = 0; i cotton.length(); ) {

                        int index = i;

                        for (int j = 0; j small.length(); j++) {

                            if (index cotton.length() && cotton.charAt(index) == small.charAt(j)) {

                                index++;

                            } else {

                                break;

                            }

                        }

                        if (index - i == small.length()) {

                            count++;

                            i += small.length();

                        } else {

                            i++;

                        }

                    }

                    System.out.println(count);

                }

            }

        }
发表于 2023-08-15 21:27:35 回复(0)
Java
iceSeasalt头像 iceSeasalt 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { 
            String str = in.next();
            String t = in.next();
            System.out.println(sub(str,t));
        }
    }

    public static int sub(String str,String t){
        int count = 0;
        int i = str.indexOf(t);
        while(i != -1){
            count++;
            i = str.indexOf(t, i + t.length());
        }
        return count;
    }
}

发表于 2023-05-06 09:34:40 回复(0)
txy_钟琛头像 txy_钟琛 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str1 = scanner.next();
            String str2 = scanner.next();
            int length2 = str2.length();
            int length1 = str1.length();
            int count = 0;
            for (int i = 0; i < length1; i++) {
                //若第一个字母相同则继续比较下去
                if (str1.charAt(i) == str2.charAt(0)) {
                    boolean flag = true;
                    int j = 0;
                    for (j = 0; j < length2; j++) {
                        if ( i + j < length1&& str2.charAt(j) != str1.charAt(j + i) ) {
                            flag = false;
                            break;
                        }
                    }
                    if ( i + j < length1+1 && flag) {
                        count++;
                        i += length2 - 1;
                    }
                } else {
                    //若第一个字母都不同就跳下一个字母
                    continue;
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2022-03-30 21:39:22 回复(0)
ID84848484头像 ID84848484
// write your code here
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
           
        String str1=in.next();
        String str2=in.next();
       
        if(str1.length() < str2.length())
        {
            System.out.println(0);
        }
       
        else
        {
           
        int ret=0;
        for(int i=0;i<=str1.length()-str2.length();)
            {
            if(str1.substring(i,i+str2.length()).equals(str2))
                {
                ret++;
                i=i+str2.length();
                }
            else
                i++;
            }
           
        System.out.println(ret);
        }
      }
   }
}

发表于 2019-05-10 23:43:00 回复(0)
C/C++
naiths头像 naiths 
// 直接利用string中的find逐个查找
#include <iostream>
#include <string>
using namespace std;

int main() 
{
    string s, t;
    while (cin >> s >> t) 
    {
        int count = 0;
        auto pos = s.find(t, 0);
        while(pos != string::npos)
        {
            count++;
            // 下一次开始查找的位置是pos + t的大小
            pos = s.find(t, pos + t.size());
        } 
        cout << count << endl;
    }
}

发表于 2023-08-16 16:29:43 回复(0)
Java
求求一个大厂offer头像 求求一个大厂offer 
import java.util.Scanner;

/*
 * 剪花布条
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str1 = sc.next(); //花布条
            String str2 = sc.next(); //小饰条
            int fast = 0, slow = 0; //快慢指针
            int count = 0;
            for (int i = 0; i < str1.length(); i++) {
                if (str1.substring(slow, fast + 1).contains(str2)) {
                    count++;
                    slow = fast +
                           1; //开始新的寻找，往后继续寻找,前面找过的部分不要
                    fast++;
                } else {
                    fast++;//往后继续寻找
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2023-04-12 20:14:42 回复(0)
Java
侬是一个好人头像 侬是一个好人 
import java.util.*;
import java.io.*;

public class Main{
    
    public static int cut(String str1,String str2){
        int i = str1.indexOf(str2);
        if(i == -1){  //查找终止条件
            return 0;
        }
        return 1 + cut(str1.substring(i+str2.length()),str2);
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String str;
        while((str = reader.readLine()) != null){
            int index = str.indexOf(" ");
            String str1 = str.substring(0,index);
            String str2 = str.substring(index+1);
            int tmp = cut(str1,str2);
            System.out.println(tmp);
        }
    }
}

发表于 2023-02-15 14:01:23 回复(0)
未见花闻头像 未见花闻 
// write your code here

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (sc.hasNext()) {
            String s = sc.nextLine();
            String[] ss = s.split(" ");
            String s1 = ss[0];
            String s2 = ss[1];
            int n = s2.length();
            int ans = 0;
            int i = s1.indexOf(s2);
            while (i != -1) {
                ans++;
                s1 = s1.substring(i + n);
                i = s1.indexOf(s2);
            }
            System.out.println(ans);
        }
    }
}

发表于 2022-09-30 20:04:32 回复(0)
爱干饭的猿头像 爱干饭的猿
运用String.contains（）和String.replaceFirst（）方法 
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.next();
            String ret = in.next();
            int count = 0;
            while(str.contains(ret)){
                count ++;
                str = str.replaceFirst(ret," ");
            }
            System.out.println(count);
        }
        in.close();
    }
}


发表于 2022-06-01 18:04:28 回复(0)
Java
来学习的小张头像 来学习的小张 
import java.util.*;
public class Main{
    public static int fun(String s,String t){
        int i = s.indexOf(t);
        if(i == -1){
            return 0;
        }
        return 1 + fun(s.substring(i + t.length()),t);
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s = sc.next();
            String t = sc.next();
            int res = fun(s,t);
            System.out.println(res);
        }
    }
}
暴力搜索

编辑于 2022-05-15 21:08:48 回复(0)
C/C++
AlbatrossLy头像 AlbatrossLy 
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str1, str2;
    while (cin >> str1 >> str2)
    {
        int len1 = str1.size();
        int len2 = str2.size();
        unsigned int idx = 0;
        int count = 0;
        while (idx < len1)
        {
            idx = str1.find(str2, idx);
            // 这里如果没有判断，会出现死循环情况
            if (idx >= len1)
                break;
            idx += len2;
            count++;
        }
        cout << count << endl;
    }

    return 0;
}

发表于 2021-11-17 21:03:54 回复(0)
一城烟雨柳色青头像 一城烟雨柳色青 
#include<iostream>
#include<string>
using namespace std;

int main()
{
	string s1, s2;
	while (cin >> s1 >> s2)
	{
		int len = s2.size(), nums = 0, i = 0;
		while (i < s1.size())
		{
			string s3 = s1.substr(i, len);  
			if (s3 == s2)   //是就++nums，并且删除对应的字串
			{
				++nums;
				s1.erase(i, len);
				--i;       //这是为了下次继续从i处开始
			}
			++i;
		}
		cout << nums << endl;
	}
	return 0;
}

发表于 2020-07-10 18:59:03 回复(0)
我不是董皓宇。头像 我不是董皓宇。

三种解法：

第一种：简单的字符串匹配算法：时间复杂度O（M*N） 
#include<iostream>
#include<string>
using namespace std;

int main()
{
    string s,t;
    while(cin>>s>>t)
    {
        int count = 0;
        for(int i = 0; i < s.size(); i++)
        {
            int j = 0, k = i;
            while(s[k] == t[j] && k < s.size())
            {
                ++k;++j;
            }
            if(j == t.size())
            {
                count++;
                i = k-1;
            }
        }
        cout<<count<<endl;
    }
}
第二种：用C++ STL接口中的find函数 
int main()
{
    string s,t;
    while(cin>>s>>t)
    {
        int count = 0;
    while (s.find(t) != string::npos)
        {
            count++;
            s.erase(s.find(t), t.size());
        }
        cout<<count<<endl;
    }
}
第三种：KMP算法 时间复杂度O(M+N),实现比较麻烦，可以看一下下面的视频
编辑于 2020-03-05 14:57:10 回复(0)
提交观点

问题信息

字符串 查找
难度：
32条回答 18414浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号