Pagini recente » Cod sursa (job #2356836) | Cod sursa (job #247359) | Cod sursa (job #1154653) | Cod sursa (job #2634819) | Cod sursa (job #632327)
Cod sursa(job #632327)
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
int n,m,i,j,k,pi[2000001],q,sol[2000001];
int main() {
f >> a;f >> b;
n=a.size();m=b.size();
a=' '+a;b=' '+b;
k=0;pi[1]=0;
for (i=2;i<=n;i++) {
while (k>0 && a[k+1]!=a[i])
k=pi[k];
if (a[k+1]==a[i])
k++;
pi[i]=k;
}
q=0;
for (i=1;i<=m && sol[0]<1000;i++) {
while (q>0 && a[q+1]!=b[i])
q=pi[q];
if (a[q+1]==b[i])
q++;
if (q==n) {
sol[++sol[0]]=i-n;
q=pi[n];
}
}
g << sol[0] << '\n';
for (i=1;i<=sol[0];i++)
g << sol[i] << ' ';
f.close();g.close();
return 0;
}