Pagini recente » Cod sursa (job #1917996) | Cod sursa (job #231402) | Cod sursa (job #1000340) | Cod sursa (job #1106782) | Cod sursa (job #2280537)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,a,b;
int pi[200005],r[1005];
string A,B,s;
void prefix_func()
{
pi[1]=0;
int k=0;
for(int q=2;q<=a;q++)
{
while(k>0 && A[k+1]!=A[q])
k=pi[k];
if(A[k+1]==A[q])
k++;
pi[q]=k;
}
}
void KMP_Matcher()
{
prefix_func();
int q=0;
for(int i=1;i<=b;i++)
{
while(q>0 && A[q+1]!=B[i])
q=pi[q];
if(A[q+1]==B[i])
q++;
if(q==a-1)
{
n++;
if(n<=1000) r[n]=i-a+1;
q=pi[q];
}
}
}
int main() {
A=" "; B=" ";
getline(fin, s);
A+=s;
getline(fin, s);
B+=s;
a=(int)A.size();
b=(int)B.size();
if(a>b)
{ fout<<0<<"\n"; return 0; }
if(A==B)
{ fout<<1<<"\n"<<0<<"\n"; return 0; }
KMP_Matcher();
fout<<n<<"\n";
int l=min(n,1000);
for(int i=1;i<=l;i++)
fout<<r[i]<<" ";
}