时间限制: 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%测试点的字符串中含有彩蛋
注意题意理解，我开始理解错了。
构造测试样例：
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; } else k=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; }
