Pagini recente » Cod sursa (job #243557) | Cod sursa (job #2341821) | Cod sursa (job #697003) | Cod sursa (job #2328595) | Cod sursa (job #1631266)
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
int pi[2000010],sol[1005],n,m,total,i;
void buildprefix()
{
int i, q = 0;
pi[0]=-1;
for (i = 1; i <m; ++i)
{
q=pi[i-1];
while (q>=0 && a[q] != a[i])
q = pi[q];
pi[i] = q+1;
}
}
int main()
{
getline(fin, a);
getline(fin, b);
m = a.length();
n = b.length();
if(m > n)
{ fout<<"0"; return 0; }
buildprefix();
int q = 0;
for ( i = 0; i<n; ++i)
{
while (q>0 && a[q] != b[i])
q = pi[q-1];
//if(q<0) q=0;
if (a[q] == b[i])
++q;
if (q == m)
{
q = pi[m-1];
++total;
if(total < 1000)
sol[total] = i-m+1;
}
}
fout<<total<<"\n";
for(i=1;i<=min(total, 1000); i++)
fout<<sol[i]<<" ";
return 0;
}