Pagini recente » Cod sursa (job #162210) | Cod sursa (job #2139130) | Cod sursa (job #1665423) | Cod sursa (job #2604207) | Cod sursa (job #3257998)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int m, n, k, i, f[2000001], N, r, v[1001];
char p[2000001], t[2000001];
void prefix(){
f[0]=-1;
for(i=1;i<=m;i++){
k=f[i-1];
while(k>=0&&p[k]!=p[i-1]){
k=f[k];
}
if(k==-1)
f[i]=0;
else
f[i]=k+1;
}
}
int kmp(){
k=0;
while(i<=n-m&&k<m){
if(t[i+k]==p[k]) k++;
else if(k==0) i++;
else{
i+=k-f[k];
k=f[k];
}
}
if(k==m) return i;
return -1;
}
int main(){
fin>>p;
fin>>t;
m=strlen(p);
n=strlen(t);
prefix();
k=0;
i=0;
while(r!=-1){
r=kmp();
if(r!=-1){
N++;
if(N<=1000)
v[N]=r;
}
i++;
}
fout<<N<<endl;
for(i=1;i<=1000&&i<=N;i++) fout<<v[i]<<' ';
return 0;
}