Pagini recente » Cod sursa (job #656708) | Cod sursa (job #2807143) | Cod sursa (job #677107) | Cod sursa (job #1075395) | Cod sursa (job #2736499)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
char a[2000001];
char b[2000001];
int suff[2000001];
int sol[1001];
void build (int m)
{
int n=0;
int i;
suff[0]=0;
for (i=1;i<m;i++){
if (a[i]==a[n]){
n++;
suff[i]=n;
}
else{
if (n){
n=suff[n-1];
i--;
}
else{
suff[i]=0;
}
}
}
}
int main()
{
cin>>a;
cin>>b;
int s=0;
int m=strlen(a);
int n=strlen(b);
build(m);
int i=0,j=0;
while(i<n){
if (a[j]==b[i]){
i++;
j++;
}
if (j==m){
s++;
if (s<=1000) sol[s]=i-m;
j=suff[j-1];
}
else {
if (i<n && a[j]!=b[i]){
if (j) j=suff[j-1];
else i++;
}
}
}
cout<<s<<"\n";
for (i=1;i<=min(s,1000);i++){
cout<<sol[i]<<" ";
}
return 0;
}