问题 G: 字符串
时间限制: 1 Sec 内存限制: 128 MB
提交 状态
题目描述
人类的本质是——复读机。
众所周知，Tweetuzki喜欢复读。
有时候，Tweetuzki会得到某个字符串s。这时他会把s不断重复不断重复连成一个无限长的串。比如说，Tweetuzki现在得到一个串
xrjakioi
，他会一直复读，那么形成的字符串就是：我有一个绝妙的无限长的串，可惜这里的空白太小我写不下
xrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioixrjakioi
同样众所周知的是，发送消息的字长是有限制的。如果要发送的串超过了长度限制，那么就只会发送这个串的一个前缀。比如说对于上述无限长的字符串，若长度限制是13，那么实际发出去的字符串是
xrjakioixrjak。
现在Tweetuzki发出去了一个字符串T，但他不能确定他复读的字符串是什么了。他唯一知道的是，他复读的字符串，一定是m个字符串中的一个。他希望知道，在这m个字符串中，有多少个字符串可能是Tweetuzki复读后发送出去的呢？
输入
输入文件将会遵循以下格式：
n
T
m
S1
S2
?
Sm
第一行输入一个字符 n (1≤n≤106)，表示发送消息的长度限制。
第二行输入一个长度为 n 的字符串 T，表示 Tweetuzki 发送的消息。
第三行输入一个数 m (1≤m≤106)。表示字符串个数。
接下来 m 行，每行输入一个字符串 S (1≤∣S∣≤n,∑∣S∣≤107)。
保证所有字符串中仅出现小写字母。
输出
输出一行一个整数，表示 m 个串中经过复读并发出后能够形成 T 的串个数。
样例输入 Copy
9
abaabaaba
3
aba
ab
abaaba
样例输出 Copy
2
提示
Subtask #1: 1≤n,m≤100。
Subtask #2: 1≤n,m≤1000。
Subtask #3: T和S的每一个位置上的字母在 a 到 z 中均匀随机，且该档只有 7 个测试点。
Subtask #4: 无特殊性质。
保证约 40%测试点的字符串中含有彩蛋
找最小循环节，那就是KMP，套模板
注意题意理解，我开始理解错了。
构造测试样例：
2
ab
3
aba
ab
abaaba答案【3】
9
abcdeabcdeabcde
1
abcdeabc
答案【1】
AC代码：一直错在main里面的if else
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N = 10000010;
int Next[N];
char s[N];
char t[N];
int tlen,len;
void getNext(char s[N])
{int j=0,k=-1;Next[0]=-1;while(j<tlen){if(k==-1||s[j]==s[k]){Next[++j]=++k;}elsek=Next[k];}
}int main()
{int n;scanf("%d",&n);scanf("%s",s);tlen=strlen(s);len=tlen;getNext(s);int kk=tlen-Next[tlen];//cout<<"kk"<<kk<<endl;int m;scanf("%d",&m);int ans=0;for(int i=1; i<=m; i++){scanf("%s",t);tlen=strlen(t);if(tlen<len){if(tlen>kk&&(tlen%kk==0)){getNext(t);int ik=tlen-Next[tlen];// cout<<"ik"<<ik<<endl;if(ik==kk&&tlen%ik==0){ans++;}}else if(kk==tlen){int f=1;for(int j=0; j<tlen; j++){if(t[j]!=s[j]){f=0;break;}}if(f==1)ans++;}}else if(tlen>=len)///题意理解错了。。。{int f=1;for(int i=0; i<len; i++){if(s[i]!=t[i]){f=0;break;}}if(f==1)ans++;}}cout<<ans<<endl;return 0;
}