Pagini recente » Cod sursa (job #502422) | Cod sursa (job #2306097) | Cod sursa (job #1787541) | Cod sursa (job #350678) | Cod sursa (job #1944008)
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,j,k;
int q[2000005],sol[2000005];
char s1[2000005],s2[2000005];
int main(){
fin>>s1;
fin>>s2;
n=strlen(s1);
m=strlen(s2);
for(i=1;i<n;i++){
while(k>0&&s1[i]!=s1[k]){
k=q[k-1];
}
if(s1[i]==s1[k]){
k++;
}
q[i]=k;
}
k=0;
for(i=0;i<m;i++){
while(k>0&&s2[i]!=s1[k]){
k=q[k-1];
}
if(s2[i]==s1[k]){
k++;
}
if(k==n){
k=q[n-1];
sol[++j]=i-n+1;
}
}
fout<<j<<"\n";
for(i=1;i<=j;i++){
fout<<sol[i]<<" ";
}
return 0;
}