Pagini recente » Cod sursa (job #440850) | Cod sursa (job #1419188) | Cod sursa (job #1163832) | Cod sursa (job #1024016) | Cod sursa (job #1760110)
#include<iostream>
#include<string>
#include<fstream>
using namespace std;
string p, t;
int i,j,k,n,prefix[2000005], sol[1005];
int main(void) {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
getline(cin,p);
p=' '+p;
getline(cin,t);
t=' '+t;
prefix[0]=-1;
prefix[1]=0;
for (i=2; i<p.length(); ++i) {
k=prefix[i-1];
while (k>=0 && p[k+1]!=p[i]) k=prefix[k];
prefix[i]=k+1;
}
k=0;
for (i=1; i<t.length(); ++i) {
while (k>=0 && t[i]!=p[k+1]) k=prefix[k];
++k;
if (k==p.length()-1) {
++n;
if (n<=1000) sol[n]=i-p.length()+1;
k=prefix[k];
}
}
cout<<n<<"\n";
for (i=1; i<=min(n,1000); ++i) cout<<sol[i]<<" ";
return 0;
}