Pagini recente » Cod sursa (job #2624854) | Cod sursa (job #251488) | Cod sursa (job #87715) | Cod sursa (job #508778) | Cod sursa (job #2720996)
#include <bits/stdc++.h>
using namespace std;
ifstream fcin("strmatch.in");
ofstream fcout("strmatch.out");
char pat[2000003],M[2000003];
int sol[1069],prefix[2000003],nr,n,m;
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;
}
void solve()
{
for(int j=0,i=0;i<m;){
if(M[i]==pat[j]){
i++;
j++;
}
else if(j==0){
i++;
}
else{
j=prefix[j-1];
}
if(j==n){
nr++;
if(nr<=1003)
sol[nr]=i-n;
}
}
}
int main()
{
fcin.getline(pat,100000);
fcin.getline(M,100000);
n=strlen(pat);
m=strlen(M);
// if(caz_special())
// return 0;
construire();
solve();
fcout<<nr<<endl;
for(int i=1;i<=min(nr,1000);i++)
fcout<<sol[i]<<' ';
return 0;
}