Pagini recente » Cod sursa (job #1253694) | Cod sursa (job #590778) | Cod sursa (job #895823) | Cod sursa (job #2893688) | Cod sursa (job #2719127)
#include <iostream>
#include<fstream>
#include<cstring>
using namespace std;
char s[200001], sm[2000001];
int pi[200001], r[1001];
int main() {
int m, k, i, n, ans;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(s, 200001);
m=strlen(s);
fin.getline(sm, 200001);
n=strlen(sm);
for(i=m;i>=1;i--) {
s[i]=s[i-1];
}
for(i=n;i>=1;i--) {
sm[i]=sm[i-1];
}
k=0;
pi[1]=0;
for(i=2;i<=m;i++) {
while(k>0 && s[k+1]!=s[i]) {
k=pi[k];
}
if(s[k+1]==s[i]) {
k++;
}
pi[i]=k;
}
int q=0;
for(i=1;i<=n;i++) {
while(q>0 && s[q+1]!=sm[i]) {
q=pi[q];
}
if(s[q+1]==sm[i]) {
q++;
}
if(q==m) {
if(ans<1000){
ans++;
r[ans]=i-m+1;
}
else {
break;
}
}
}
fout<<ans<<"\n";
for(i=1;i<=ans;i++) {
fout<<r[i]-1<<" ";
}
return 0;
}