Pagini recente » Cod sursa (job #1202265) | Cod sursa (job #388557) | Cod sursa (job #2712073) | Cod sursa (job #3214181) | Cod sursa (job #2490163)
#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;
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;i++)if(lps[i]==lens)fout<<i-2*lens<<" ";
return 0;
}