Pagini recente » Cod sursa (job #869554) | Cod sursa (job #2791453) | Cod sursa (job #193514) | Istoria paginii runda/simulare_oji_clasa_x/clasament | Cod sursa (job #1135535)
#include<fstream>
#include<string>
using namespace std;
const int maxn = 2000005;
char s[maxn], t[maxn];
int a[maxn],x[maxn];
main(){
// ifstream fin("strmatch.in");
// ofstream fout("strmatch.out");
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
// scanF("%d %d",t,s);
fgets(t, sizeof(t), stdin);
fgets(s, sizeof(s), stdin);
// fin>>t>>s;
int m=0,m1=0,M=0;
for (; (t[M] >= 'A' && t[M] <= 'Z') || (t[M] >= 'a' && t[M] <= 'z')|| (t[M] >= '0' && t[M] <= '9'); ++M);
m=M;M=0;
for (; (s[M] >= 'A' && s[M] <= 'Z') || (s[M] >= 'a' && s[M] <= 'z')|| (s[M] >= '0' && s[M] <= '9'); ++M);
m1=M;
int k=0,n=0;
a[0]=0;
for(int i=1;i<m;i++){
while(k && t[k]!=t[i])k=a[k];
if(t[k]==t[i])k++;
a[i]=k;
}
k=0;
for(int i=0;i<m1;i++){
while(k && t[k]!=s[i])k=a[k-1];
if(t[k]==s[i])k++;
if(k==m){
k=a[m-1];
n++;
if(n<1002)
x[n]=i-m+1;
}
}
// fout<<n<<"\n";
printf("%d\n",n);
if(n>1000)n=1000;
for(int i=1;i<=n;i++)//fout<<x[i]<<" ";
printf("%d ",x[i]);
}