Pagini recente » Cod sursa (job #2703341) | Cod sursa (job #1814733) | Cod sursa (job #1800712) | Cod sursa (job #2227252) | Cod sursa (job #1206984)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int c, d,nr;
int L[2000001],rasp[1001];
void prefix()
{
int i,k;
for(i=1; i<c; i++)
{
k=L[i-1];
while(k>-1 && a[k+1]!=a[i])
k=L[k];
if(a[i]==a[k+1])
k++;
L[i]=k;
}
}
void kmp()
{
int i,t,k=-1;
for(t=1; t<d; t++)
{
while(k>-1 && b[t]!=a[k+1])
k=L[k];
if(b[t]==a[k+1])
k++;
if(k==c-1 && nr<1000)
{
rasp[nr]=t-c+1;
nr++;
k=L[k];
}
}
}
int main()
{
getline(in, a);
getline(in, b);
c=a.length();
d=b.length();
for(int i=0; i<c; i++)
L[i]=-1;
prefix();
kmp();
if(c>d)
out<<0;
else
{
out<<nr<<endl;
if(nr<1000)
for(int i=0; i<nr; i++)
out<<rasp[i]<<" ";
else
for(int i=0; i<1000; i++)
out<<rasp[i]<<" ";
}
return 0;
}