Pagini recente » Cod sursa (job #3221625) | Cod sursa (job #936223) | Cod sursa (job #1150929) | Cod sursa (job #1780435) | Cod sursa (job #1631289)
#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;
pi[1]=0;
for (i=2; i<=m; ++i)
{
q=pi[i-1];
while (q>=0 && a[q+1] != a[i])
q = pi[q];
pi[i] = q+1;
}
}
int main()
{
getline(fin, a);
getline(fin, b);
m = a.length();
n = b.length();
a=' '+a;
b=' '+b;
if(m > n)
{ fout<<"0"; return 0; }
buildprefix();
int q = 0;
for ( i = 1; i<=n; ++i)
{
while (q>0 && a[q+1] != b[i])
q = pi[q];
if (a[q+1] == b[i])
++q;
if (q == m)
{
q = pi[m];
++total;
if(total <= 1000)
sol[total] = i-m;
}
}
fout<<total<<"\n";
for(i=1;i<=min(total, 1000); i++)
fout<<sol[i]<<" ";
return 0;
}