企业网站建设协议,开网站建设公司好,培训机构营销方案,十大网站管理系统cyk追楠神系列三
Description 众所周知#xff0c;cyk给楠神写了一封信表白。作为有一个有礼貌的五好青年#xff0c;楠神当然得给 cyk 写一封回信咯#xff0c;俗称“好人信”。
楠神是一个非常有文采的人#xff0c;他在信里引用了很多名言来安慰 cyk#xff0c;有时候…cyk追楠神系列三
Description 众所周知cyk给楠神写了一封信表白。作为有一个有礼貌的五好青年楠神当然得给 cyk 写一封回信咯俗称“好人信”。
楠神是一个非常有文采的人他在信里引用了很多名言来安慰 cyk有时候他觉得一句话很好的话他会引用很多次。现在他想考考 cyk在告诉 cyk 里面每句名言的情况下看看 cyk 能不能找到每局名言在信里被引用了多少次。如果能找到的话说明 cyk 也是一个有涵养的人楠神对 cyk 的好感度就会增加。
cyk 语文和眼力那么差当然不行咯所以你赶快帮帮 cyk 吧
Input 输入数据有多组数据组数不超过 50到 EOF 结束。
每组数据第一行输入一串字符串代表楠神写的回信长度不超过 10^6。
第二行输出 n (1 n 100)接下来 n 行每行一个字符串代表楠神引用的名言长度不超过 10^6。
Output 每组数据中对于每句名言输出他被引用的次数每个答案占一行。
Samples Sample #1 Input In fact, maybe we can become good friend, but don’t lose hear for yourselves, when there is a will, there is a way, you can become a better man~ 1 when there is a will, there is a way Output 1 Hint 子串在主串中的匹配允许重叠。
分析
感觉就是简单KMP但是用C一直不对烦死啦 问题主要就是输入的时候 错误的C版本
#include bits/stdc.h
#include string.h
using namespace std;
const int N1e6 10;
int n,t,m,j,i,sum,b;
char s1[N],s2[N];
int next1[N];
void getnext(){int i0,j-1;int len2strlen(s2);next1[0]-1;while(ilen2){if(j-1||s2[i]s2[j]){i;j;next1[i]j;}else jnext1[j];}
}
void kmp(){int i0,j0,sum0;int len1strlen(s1);int len2strlen(s2);while(ilen1jlen2){if(j-1||s1[i]s2[j]){i;j;}else jnext1[j];if(jlen2)sum;}coutsumendl;
}
int main(){while(cin.getline(s1,256)){cinn;getchar();for(int i0;in;i){
// memset(s2,0,sizeof(s2));cin.getline(s2,256);getnext();kmp();}}return 0;
}正确的C版本
#include stdio.h
#include stdlib.h
#include string.h
int next[1000005];
void get_next(char s2[])
{int i0,j-1;int len2strlen(s2);next[0]-1;while(ilen2){if(j-1||s2[i]s2[j]){i;j;next[i]j;}else{jnext[j];}}
}
void kmp(char s1[],char s2[])
{int i0,j0,cn0;int len1strlen(s1),len2strlen(s2);get_next(s2);while(ilen1jlen2){if(j-1||s1[i]s2[j]){i;j;}else{jnext[j];}if(jlen2){cn;}}printf(%d\n,cn);
}
int main()
{char s1[1000001],s2[1000001];int n;while(gets(s1)!NULL){scanf(%d,n);getchar();while(n--){memset(s2,0,sizeof(s2));gets(s2);kmp(s1,s2);}}return 0;
}
