Pagini recente » Cod sursa (job #2059562) | Cod sursa (job #2032134) | Cod sursa (job #2032139) | Cod sursa (job #9839) | Cod sursa (job #2720888)
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("strmatch.in");
ofstream fcout("strmatch.out");
char pat[2000001],M[2000001];
int sol[1002],prefix[2000001],nr,n,m;
//void afis(char x[])
//{
// cout<<endl;
// for(int i=0;i<strlen(x);i++)
// fcout<<i<<' ';
// cout<<endl;
// for(int i=0;i<strlen(x);i++)
// cout<<x[i]<<' ';
// cout<<endl;
//}
void solve()
{
int j=0;
for(int i=0;i<m;){
if(M[i]==pat[j]){
if(j==n-1){
nr++;
if(nr<=1000)
sol[nr]=i-n+1;
j=prefix[j-1];
}
else{
i++;
j++;
}
}
else if(j>0){
j=prefix[j-1];
}
else{
i++;
}
}
}
void construire()
{
int j=0,i=1;
prefix[0]=0;
for(i=1;i<n;){
if(pat[i]==pat[j]){
prefix[i]=j+1;
i++,j++;
}
else{
if(j!=0)
j=prefix[j-1];
else{
prefix[i]=0;
i++;
}
}
}
}
bool caz_special()
{
if(m==n){
if(strcmp(M,pat)==0)
fcout<<1<<endl<<0<<' ';
else
fcout<<0;
return 1;
}
if(n>m){
fcout<<0;
return 1;
}
return 0;
}
int main()
{
fcin.getline(pat,100000);
fcin.getline(M,100000);
n=strlen(pat);
m=strlen(M);
// if(caz_special())
// return 0;
construire();
// for(int i=0;i<n;i++)
// cout<<prefix[i]<<' '; cout<<endl;
solve();
fcout<<nr<<endl;
for(int i=1;i<=nr && i<=1000;i++)
fcout<<sol[i]<<' ';
return 0;
}