Pagini recente » Cod sursa (job #1146402) | Cod sursa (job #1217139) | Cod sursa (job #607821) | Cod sursa (job #1545015) | Cod sursa (job #2307642)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int L=2000001;
int sol[1001], pi[L+1];
char txt[L+1], pat[L+1];
int Nsol, n, m;
void prefix_function()
{
int k=0;
pi[1]=0;
for(int q=2; q<=m; ++q)
{
while(k>0 && pat[k+1]!=pat[q]) k=pi[k];
if(pat[k+1]==pat[q]) ++k;
pi[q]=k;
}
}
int main()
{
fin.getline(pat+1, L);
fin.getline(txt+1, L);
m=strlen(pat+1);
n=strlen(txt+1);
prefix_function();
int q=0;
for(int i=1; i<=n; ++i)
{
while(q>0 && txt[i]!=pat[q+1]) q=pi[q];
if(txt[i]==pat[q+1]) ++q;
if(q==m)
{
q=pi[m];
++Nsol;
if(Nsol<=1000) sol[Nsol]=i-m;
}
}
fout<<Nsol<<"\n";
for(int i=1; i<=min(1000, Nsol); ++i) fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}