Pagini recente » Cod sursa (job #1399811) | Cod sursa (job #1735500) | Cod sursa (job #1219556) | Cod sursa (job #538132) | Cod sursa (job #2490219)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s[4000005],t[2000005]; int n,len,lps[4000002],i,lens,lent,nr,contor;
int main(){
fin>>s>>t; lens=strlen(s); lent=strlen(t);
strcat(s,"#"); strcat(s,t); n=lens+lent+1;
len=lps[0]=0; i=1;
while(i<n){
if(s[i]==s[len]) {lps[i++]=++len; if(lps[i-1]==lens && i>=lens+1)nr++;}
else{
if(len)len=lps[len-1];
else lps[i++]=0;
}
}
fout<<nr<<'\n';
for(i=lens+1;i<lens+1+lent && contor<=999;i++)if(lps[i]==lens){fout<<i-2*lens<<" ";contor++;}
return 0;
}