Pagini recente » Cod sursa (job #2353538) | Cod sursa (job #2409228) | Cod sursa (job #976217) | Cod sursa (job #216362) | Cod sursa (job #1635297)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char patern[2000004], text[2000004];
int pi[2000004], pos[2000004], i, n, m, ind, sol;
void genereaza()
{
int i, q=0;
for(i=1; i<n; i++)
{
while(q&&patern[i]!=patern[q]) q=pi[q-1];
if(patern[i]==patern[q])
{
q++;
}
pi[i]=q;
}
}
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(patern, 2000002);
fin.getline(text, 2000002);
n=strlen(patern);
m=strlen(text);
genereaza();
ind=i;
for(i=0; i<m; i++)
{
while(text[i]!=patern[ind]&&ind) ind=pi[ind-1];
if(text[i]==patern[ind]) ind++;
if(ind==n)
{
++sol;
if(sol<=1000) pos[sol]=i-n;
}
}
fout<<sol<<"\n";
for(i=1; i<=sol; i++) fout<<pos[i]+1<<" ";
return 0;
}