当前位置:   article > 正文

KMP算法(题目)

KMP算法(题目)

A. 子串位置

题目描述:

给定一个父字符串 s 和子字符串 p ,请按照从前向后的顺序,请求出 p 在 s 中所有出现的起始位置。

例如:s=ABADABCEABABA,p=ABA,则求解的结果是:1 9 11 。

输入:

第 1 行读入一个仅包含大写字母的字符串 s;

第 2 行读入一个仅包含大写字母的字符串 p ;

s 和 p 均是长度不超过 106 的字符串。

输出:

输出 1 行,按题意输出 p 在 s 中出现的位置,数字之间用空格隔开。

样例:

输入:

ABADABCEABABA
ABA

输出:

1 9 11

代码如下:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e6 + 10;
  4. char s[N],p[N];
  5. //ne:存储p字符串前i个字符的最大前缀和后缀相同的长度
  6. int ne[N];
  7. int main(){
  8. scanf("%s%s",s+1,p+1);
  9. //计算ne数组
  10. ne[0] = ne[1] = 0;
  11. int lens = strlen(s+1),lent = strlen(p+1);
  12. for(int i = 1,j = 0;i < lent;i++){
  13. while(j && p[i+1]!=p[j+1]) j = ne[j];
  14. if(p[i+1] == p[j+1]) j++;
  15. ne[i+1] = j;
  16. }
  17. //尝试匹配父子字符串
  18. for(int i = 0,j = 0;i < lens;i++){
  19. while(j && s[i+1] != p[j+1]) j = ne[j];
  20. if(s[i+1] == p[j+1]) j++;
  21. //配对成功,输出起始位置
  22. if(j == lent){
  23. printf("%d ",i + 1 - lent + 1);
  24. j = ne[j];
  25. }
  26. }
  27. return 0;
  28. }

B. 最多子串重复次数

题目描述:

给定若干个长度≤106 的字符串,询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如:ababab 则最多有 3 个 ab 连接而成。

输入:

输入若干行(所有行的字符串的长度之和≤107),每行有一个字符串,字符串仅含英语小写字母。特别的,字符串可能为 . 即一个半角句号,此时输入结束。

输出:

对于每行输入,输出一个整数,代表计算的结果。

样例:

输入:

abcd
aaaa
ababab
.

输出:

1
4
3

代码如下:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e6+10;
  4. char s[N];
  5. int ne[N];
  6. int main(){
  7. while(scanf("%s",s+1)&&s[1]!='.'){
  8. ne[0]=ne[1]=0;
  9. int len=strlen(s+1);
  10. for(int i=1,j=0;i<len;i++){
  11. while(j&&s[i+1]!=s[j+1]) j=ne[j];
  12. if(s[i+1]==s[j+1]) j++;
  13. ne[i+1]=j;
  14. }
  15. if(len%(len-ne[len])==0) printf("%d\n",len/(len-ne[len]));
  16. else printf("%d\n",1);
  17. }
  18. return 0;
  19. }

C. 前缀和后缀

题目描述

给定若干由小写字母组成的字符串(这些字符串总长 ≤4×105 ),在每个字符串中求出所有既是前缀又是后缀的子串长度。

例如:ababcababababcabab,既是前缀又是后缀的:

ab,abab,ababcabab,ababcababababcabab 。

输入:

输入若干行,每行一个字符串。

输出:

对于每个字符串,输出一行,包含若干个递增的整数,表示所有既是前缀又是后缀的子串长度。

样例:

输入:

ababcababababcabab
aaaaa

输出:

2 4 9 18
1 2 3 4 5

代码如下:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 4e5 + 10;
  4. char s[N];
  5. int ne[N];
  6. stack<int> st;
  7. int main(){
  8. while(scanf("%s",s+1) != EOF){
  9. //计算s字符串的next数组
  10. ne[0] = ne[1] = 0;
  11. int len = strlen(s+1);
  12. for(int i = 1,j = 0;i < len;i++){
  13. while(j && s[i+1] != s[j+1]) j = ne[j];
  14. if(s[i+1] == s[j+1]) j++;
  15. ne[i+1] = j;
  16. }
  17. //计算字符串s前缀和后缀相等的情况
  18. st.push(len);
  19. while(ne[len] != 0){
  20. st.push(ne[len]);
  21. len = ne[len];
  22. }
  23. //输出
  24. while(!st.empty()){
  25. printf("%d ",st.top());
  26. st.pop();
  27. }
  28. printf("\n");
  29. }
  30. return 0;
  31. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/710524
推荐阅读
相关标签
  

闽ICP备14008679号