首页 > 试题广场 >

String Matching

[编程题]String Matching
  • 热度指数：11026 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
    Finding all occurrences of a pattern in a text is a problem that arises frequently in text-editing programs.     Typically,the text is a document being edited,and the pattern searched for is a particular word supplied by the user.       We assume that the text is an array T[1..n] of length n and that the pattern is an array P[1..m] of length m<=n.We further assume that the elements of P and  T are all alphabets(∑={a,b...,z}).The character arrays P and T are often called strings of characters.       We say that pattern P occurs with shift s in the text T if 0<=s<=n and T[s+1..s+m] = P[1..m](that is if T[s+j]=P[j],for 1<=j<=m).       If P occurs with shift s in T,then we call s a valid shift;otherwise,we calls a invalid shift.      Your task is to calculate the number of vald shifts for the given text T and p attern P.

输入描述:
   For each case, there are two strings T and P on a line,separated by a single space.You may assume both the length of T and P will not exceed 10^6.


输出描述:
    You should output a number on a separate line,which indicates the number of valid shifts for the given text T and pattern P.
示例1

输入

abababab abab

输出

3
算法知识视频讲解
添加回答
pardon_hu头像 pardon_hu
不得不吐槽一下，KMP O（m+n）的耗时居然与暴力解O（m*n）的耗时差不多，看来是测例里模式串的长度m太短了，估计小于100，真要考KMP算法的话，测例中的m应该会到1e5左右，届时用暴力匹配是一定超时的
#include<iostream>
#include<string>

using namespace std;

const int MAXN = 1000010;

int nextTab[MAXN];

void getNextTab(string pattern){        // KMP获得nextTab数组
    int m = pattern.size();
    nextTab[0] = -1;
    int t = nextTab[0], j = 0;
    while(j < m){
        if(t == -1 || pattern[t] == pattern[j]){
            j++;
            t++;
            nextTab[j] = t;
        }else{
            t = nextTab[t];
        }
    }
    return ;
}
int KMP(string text, string pattern){     //KMP算法匹配
    getNextTab(pattern);
    int n = text.size(), m = pattern.size(), cnt = 0;
    int i = 0, j = 0;
    while(i < n){
        if( j == -1 || text[i] == pattern[j]){
            i++;
            j++;
        }else{
            j = nextTab[j];
        }
        if( j == m){
            cnt++;
                        //j = 0;                  //用于不可重复匹配问题，本题为可重复
            j = nextTab[j];        //用于可重复匹配问题，如ABABAB AB
        }                                //可匹配3次而不是2次
    }
    return cnt;
}
int match(string text, string pattern){        //暴力匹配
    int cnt = 0,left = -1;
    while((left = text.find(pattern,left+1)) != -1) cnt++;
    return cnt;
}

int main(){
    string text,pattern;
    while(cin>>text>>pattern){
        int cnt = match(text, pattern);
        //int cnt = KMP(text,pattern);        //实测两个方法耗时差不多
        printf("%d\n",cnt);
    }
    return 0;
}


编辑于 2020-03-01 10:50:53 回复(2)
C/C++
gq97头像 gq97

Object C

#include<stdio.h>
#include<string.h>
char text[1000000+7], pattern[1000000+7];
int next[1000000+7];
void getNext(char str[]){
    int i, j = -1, len = strlen(str);
    next[0] = -1;
    for(i = 1; i<len; i++){
        while(j != -1 && str[i] != str[j+1])
            j = next[j];
        if(str[i] == str[j+1])
            j++;
        next[i] = j;
    }
}
void kmp(){
    //pattern为要匹配的子串 
    getNext(pattern);
    int i, j = -1, ans = 0, m = strlen(text), n = strlen(pattern);
    for(i = 0; i<m; i++){
        while(j != -1 && text[i] != pattern[j+1])
            j = next[j];
        if(text[i] == pattern[j+1])
            j++;
        if(j == n-1){
            ans++;
            j = next[j];
        }
    }
    printf("%d\n", ans);
}

int main(){
    //freopen("in.txt", "r", stdin);
    scanf("%s%s", text, pattern);
    kmp();

    return 0;
}
发表于 2018-07-24 17:20:54 回复(0)
Python
华科平凡头像 华科平凡 

while True:
    try:
        a,b=input().split()
        res,judge=0,[]
        for i,v in enumerate(a[:len(a)-len(b)+1]):
            if v==b[0]:judge.append(i)
        for i in judge:
            if a[i:i+len(b)]==b:res+=1
        print(res)
    except:
        break

python3代码，测试通过。时间复杂度为O(n)2...

发表于 2017-10-06 16:04:26 回复(0)
C/C++
YhX.头像 YhX. 
#include<stdio.h>//字符串子串数量问题,不用strstr的解法
(3381)#include<string.h>
int main()
{
    char a[1000000],b[1000000];//注意堆栈溢出之类的可能是数组容量太小或者太大
    int i,j,m,n,key,num=0;
    scanf("%s",a);scanf("%s",b);
    n=strlen(a);m=strlen(b);
    for(i=0;i<n;i++)
    {
        key=1;
        for(j=0;j<m;j++)//与b字符串逐个对比
            if(a[i+j]!=b[j])//每个字符进行比较
            {key=0;break;}
        if(key==1) num++;
    }
    printf("%d",num);
    return 0;
}

发表于 2020-03-23 14:05:53 回复(0)
C/C++
SaulZhang98头像 SaulZhang98 
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string T,P;
    cin>>T>>P;
//    getline(cin,T);
//    getline(cin,P);
    int lent=T.length();
    int lenp=P.length();

    int acceql=0;
    int ans=0;
    for(int i=0;i<lent;i++){
        if(T[i]==P[acceql]&&i+lenp<=lent){
            acceql++;
            while(acceql!=lenp){
                if(T[i+acceql]!=P[acceql])
                    break;
                acceql++;
            }
            if(acceql==lenp)ans++;
            acceql=0;
        }
    }
    printf("%d\n",ans);

    return 0;
}
/*
abababab abab
*/

//KMP算法
#include <iostream>
#include <string>
#define N 10001
#define M 101
using namespace std;

int Next[M];
string a,b;

void getNext(int n){

    int i=0,j=-1;
    Next[0]=-1;
    while(i<n){
        if(j==-1||b[i]==b[j]){
            i++;
            j++;
            Next[i]=j;
        }
        else{
            j=Next[j];
        }
    }
}


int KMPSearch(int n,int m){

    int ans=0;
    int i=0,j=0;
    while(i<n){//&&j<m
        if(j==-1||a[i]==b[j]){
            i++;
            j++;
        }
        else{
            j = Next[j];
        }
        if(j==m){//一次匹配
            ans++;
            i = i-j+1;
            j = 0;
        }
    }

    return ans;
}

int main()
{

    while(cin>>a>>b){
        int lenA  = a.size();
        int lenB  = b.size();
        getNext(lenB);
        cout<<KMPSearch(lenA,lenB)<<endl;;

    }

    return 0;
}
/*
aaaaaaa
a
*/



//直接调用string.find(char c,int st);函数
#include<iostream>
using namespace std;
#include<string>

int main(){
    string s,p;
    while(cin>>s>>p){
        int cnt=0,pos=s.find(p);
        while(pos!=string::npos){//string::npos=-1,
            cnt++;
            pos = s.find(p,pos+1);
        }
        cout<<cnt<<endl;
    }
}
/*
abababab abab
*/

编辑于 2019-07-11 16:22:28 回复(0)
給迩灬微笑头像 給迩灬微笑
//这道题就是找在T字符串中包含的P字符串个数
#include<bits/stdc++.h>
using namespace std;
int main(){
    string str,info;
    while(cin>>str>>info){
        int num=0;
        int pos=-1;
        while(1){
            pos=str.find(info,pos+1);
            if(pos!=string::npos){
                num++;
            }else{
                break;
            }
        }
        cout<<num<<endl;
    }
}
发表于 2020-03-01 10:34:07 回复(0)
YoJay头像 YoJay 

	//





	//  main.cpp





	//  Nowcoder





	//





	//  Created by cuiyujie on 2019/1/3.





	//  Copyright © 2019 yujiecui. All rights reserved.





	//





	







	#include <iostream>





	#include<string.h>





	using namespace std;





	







	int main(int argc, const char * argv[]) {





	        char t[1000000];





	        char p[1000000];





	        





	        while(scanf("%s %s",t,p)!=EOF){





	                int j=0,i=0;





	                int i1=0;





	                int count=0;





	                while(i<strlen(t)){





	                        if(t[i]==p[j]){





	                                j++;





	                                i++;





	                        }





	                        else{





	                                i++;





	                                i1++;





	                        }





	                        if(j==strlen(p)){





	                                count++;





	                                j=0;





	                                i1=i1+1;





	                                i=i1;





	                        }





	                }





	                printf("%d",count);





	        }





	        





	        return 0;





	}

发表于 2019-01-03 16:45:22 回复(1)
月是故乡明_001头像 月是故乡明_001 
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

int main(){
    string a;
    string b;
    int num=0;
    int sum=0;
    cin>>a;
    cin>>b;
    int i,j;
    for(;;){ 
	num=a.find(b,num);
	if(num!=string::npos){
		++sum;
		num++;
	}else break;
	}
   
    cout<<sum;
    return 0;
}

发表于 2021-03-25 17:25:23 回复(0)
Xxxxsss头像 Xxxxsss 
#include <iostream>
(720)#include <string>
#include <algorithm>
using namespace std;

int main()
{
	string s;
	string temp;
	cin>>s;
	cin>>temp;
	int count=0;
	int i=0;
	while(1)
	{
		int f=s.find(temp,i);
		if(f==string::npos)
			break;
		else
		{
			i=f+1;
			count++;
		}
	}
	cout<<count;
}

发表于 2020-03-29 18:55:14 回复(0)
//饺子头像 //饺子
#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

int main(){
    
    string s, sub;
    while(cin >> s >> sub){
        int num = 0;
        while(s.find(sub) != string::npos){
            ++num;
            s = s.substr(s.find(sub)+1);
            
        }
        cout << num << endl;
    }
    return 0;
} 
发表于 2020-02-26 13:18:55 回复(0)
C/C++
fxzero头像 fxzero 
#include <stdio.h>
#include <string.h>
#define N 600000
char text[N];
char pattern[N];
int next[N];
void getnext(int n)
{
    int j=0,i=-1;
    next[j]=-1;
    while(j<n)
    {
        if(i==-1 || pattern[i]==pattern[j])
        {
            i++;
            j++;
            if(pattern[i]!=pattern[j])next[j]=i;
            else next[j]=next[i];
        }
        else i=next[i];
    }
}
int KMP(int m,int n)
{
    getnext(n);
    int i=0,j=0,num=0;
    while(i<m)
    {
        if(j==-1 || pattern[j]==text[i])
        {
            i++;
            j++;
        }
        else j=next[j];
        if(j==n)
        {
            num++;
            j=next[j];
        }
    }
    return num;
}
int main()
{
    while(~scanf("%s%s",text,pattern))
    {
        getchar();
        int m=strlen(text),n=strlen(pattern);
        int num=KMP(m,n);
        printf("%d\n",num);
    }
}


编辑于 2020-02-26 17:12:07 回复(0)
Lisco头像 Lisco 
#include<iostream>
using namespace std;
#include<string>

int main(){
    string s,p;
    while(cin>>s>>p){
        int cnt=0,pos=s.find(p);
        while(pos!=string::npos){
            cnt++;
            pos = s.find(p,pos+1);
        }
        cout<<cnt<<endl;
    }
}

发表于 2017-07-12 19:40:35 回复(0)
VirgilG72头像 VirgilG72

STL天下无敌 

#include <bits/stdc++.h>

using namespace std;
int main() {
		string s,t;
		cin>>s>>t;
		int count=0,i=s.find(t);
		while(i!=-1){
			count++;
			i=s.find(t,i+1);
		}
		cout<<count;
		return 0;
}


发表于 2020-03-03 21:07:24 回复(0)
子長君头像 子長君 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <stack>
using namespace std;

int main() {
    string t, p;
    cin >> t >> p;
    int num = 0;
    int pos = -1;
    while (1) {
        pos = t.find(p, pos + 1);
        if (pos != string::npos) {
            num++;
        }
        else {
            break;
        }
    }
    cout << num << endl;
    system("pause");
    return 0;
}
发表于 2019-03-03 20:33:53 回复(0)
Java
LHC0512头像 LHC0512
Java 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String ss= scanner.next();
            String s = scanner.next();
            int i=0;
            int count=0;
            while (ss.indexOf(s,i)!=-1){
                count++;
                i=ss.indexOf(s,i)+1;
            }
            System.out.println(count);
        }
    }
}


发表于 2020-03-20 11:16:51 回复(0)
zbt_123456头像 zbt_123456
regex加STL=秒杀 
#include<iostream>
#include<string>
#include<vector>
#include<regex>
using namespace std;
int main(){
    string text,pattern;
    while(cin>>text>>pattern){
        regex r(pattern);
        vector<string> v;
        for(int i=0; i<= text.size()-pattern.size();i++){
            if(regex_match( text.substr(i,pattern.size()), r ))
                v.push_back( text.substr(i,pattern.size()) );
        }
        cout<<v.size()<<endl;
    }
    return 0;
}

编辑于 2024-03-23 18:07:21 回复(0)
Python3
chong_0428头像 chong_0428 
def getNext(t):
    next = [0] * (len(t)+1)
    t = list(t)
    i, k = 0, -1
    next[0] = -1
    while i < len(t):
        if k == -1&nbs***bsp;t[i] == t[k]:
            k+=1
            i+=1
            next[i] = k
        else:
            k = next[k]
    return next

def kmp(s, t):
    i, j = 0, 0
    res =0
    next = getNext(t)
    s = list(s)
    t = list(t)
    while i < len(s) and j < int(len(t)):
        if(j == -1&nbs***bsp;s[i] == t[j]):
            i+=1
            j+=1
        else:
            j = next[j]

        if j == len(t):
            res+=1
            j = next[j]
            #return i - j
    return res
   

# while True:
#     try:
s, t = input().split()
res = kmp(s, t)
print(res)
    # except:
    #     break

编辑于 2024-03-19 18:13:11 回复(0)
最喜欢冬天的布拉德很想去北京头像 最喜欢冬天的布拉德很想去北京 
#include <iostream>
using namespace std;

int main() {
    string t, p;
    int i, loc, count, len;
    while (cin >> t) {
        cin >> p;
        count = 0;
        i = 0;
        len = t.length();
        while (i < len) {
            t = t.substr(i);
            loc = t.find(p);
            if (loc == t.npos)
                break;
            count++;
            i = loc + 1;
        }
    }
    cout << count;
}

发表于 2024-03-15 00:54:31 回复(0)
C++
无问西东gmy头像 无问西东gmy 
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAXN = 1e6;

vector<int>nextTable(MAXN);

void GetNextTable(string pattern) {                 //创建next表
    int m = pattern.size();
    int j = 0;
    nextTable[j] = -1;
    int i = nextTable[j];
    while (j < m) {
        if (i == -1 || pattern[j] == pattern[i]) {
            i++;
            j++;
            nextTable[j] = i;
        } else {
            i = nextTable[i];
        }
    }
}

int KMP(string text, string pattern) {
    GetNextTable(pattern);
    int n = text.size();
    int m = pattern.size();
    int i = 0;
    int j = 0;
    int number = 0;                             //记录匹配次数
    while (i < n) {
        if (j == -1 || text[i] == pattern[j]) { //当前字符匹配成功
            i++;
            j++;
        } else {
            j = nextTable[j];                   //当前字符匹配失败
        }
        if (j == m) {                           //模式串匹配成功
            number++;
            j = nextTable[j];
        }
    }
    return number;
}

int main() {
    string text, pattern;
    while (cin >> text >> pattern) {
        cout << KMP(text, pattern) << endl;
    }
    return 0;
}

编辑于 2024-03-01 14:56:26 回复(0)
奈良池头像 奈良池 
#include<iostream>
#include<vector>
using namespace std;

int main()
{
	string str,patern;
	cin>>str>>patern;
	int sum=0,pos=0;
	while(pos!= -1 )
	{
		pos=str.find(patern,pos); //当前位置向后找可匹配的 
		if(pos!=-1)
		{
			sum++; 
			pos++;
		}
	}
	cout<<sum;
}

发表于 2024-02-03 20:42:51 回复(0)
提交观点

问题信息

字符串
难度：
63条回答 6229浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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