CSU-1598 最长公共前缀

本文主要是介绍CSU-1598 最长公共前缀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面：

给定两个字符串s和t，现有一个扫描器，从s的最左边开始向右扫描，每次扫描到一个t就把这一段删除，输出能发现t的个数。

Input
第一行包含一个整数T（T<=50），表示数据组数。
每组数据第一行包含一个字符串s，第二行一个字符串t，字符串长度不超过1000000。

Output
对于每组数据，输出答案。

Sample Input
2
ababab
ab
ababab
ba
Sample Output
3
2

思路：

看数据范围，朴素匹配（暴力搜）肯定超时。所以用到KMP匹配。使用时注意下标的变化。

代码：

#include<bits/stdc++.h>
#define MAX 1000000
using namespace std;
char str[MAX],t[MAX];
int T,Next[MAX];//由于iostream里有next，所以数组要改名（CE三发T_T）
void get_next(char *s,int len)
{int i=0,j=-1;Next[0]=-1;while(i<len){if(j==-1||s[i]==s[j]){++i;++j;Next[i]=j;}elsej=Next[j];}
}
int KMP(char *s,char *t,int ls,int lt)
{int i=0,j=0,ans=0;while(i<ls){if(j==-1||s[i]==t[j]){++i;++j;}elsej=Next[j];if(j==lt){//区别在于找到一个匹配字符串之后不返回，继续查找之后的情况ans++;j=Next[j];}}return ans;
}int main()
{cin>>T;while(T--){memset(Next,0,sizeof(Next));cin>>str>>t;int ls=strlen(str);int lt=strlen(t);get_next(t,lt);int cnt;cnt=KMP(str,t,ls,lt);cout<<cnt<<endl;}return 0;
}

这篇关于CSU-1598 最长公共前缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---