Pagini recente » Cod sursa (job #2964035) | Cod sursa (job #518412) | Cod sursa (job #389706) | Cod sursa (job #2393211) | Cod sursa (job #2392523)
#include<bits/stdc++.h>
#define N 2000005
using namespace std;
string a,b;
int d[N],n,rs,k,ans[1030];
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>b>>a; n=b.size();
for (int i=1,j=0; i<b.size(); ++i) {
if (b[i]==b[j]) {
d[i]=d[i-1]+1;
++j;
} else {
while (j && b[i]!=b[j]) j=d[j-1];
if (b[i]==b[j]) d[i]=j+1, ++j;
}
}
b+="+";
for (int i=0, j=0; i<a.size(); ++i) {
if (a[i]==b[j]) {
++j;
} else {
while (j && a[i]!=b[j]) j=d[j-1];
if (a[i]==b[j]) ++j;
}
if (j==n && ++rs<=1000) ans[rs]=i-n+1;
}
cout<<rs<<'\n';
for (int i=1; i<=min(rs,1000); ++i) cout<<ans[i]<<" ";
return 0;
}