Pagini recente » Cod sursa (job #1207164) | Cod sursa (job #1237257) | Cod sursa (job #192065) | Cod sursa (job #1660755) | Cod sursa (job #1666033)
#include <fstream>
#include <cstring>
#define NM 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int V[1005];
char A[NM], B[NM];
int Pi[NM], n, m, ori;
void BuildPi()
{
Pi[0]=0;
int i, j=0;
for (i=1; i<n; i++)
{
while (j>0 && A[i]!=A[j])
{
j=Pi[j-1];
}
if (A[i]==A[j])
{
j++;
}
Pi[i]=j;
}
}
void KMP()
{
int i, j=0;
for (i=0; i<m; i++)
{
while (j>0 && A[j]!=B[i])
{
j=Pi[j-1];
}
if (B[i]==A[j])
{
j++;
}
if (j==n)
{
ori++;
V[ori]=i-n+1;
if (ori==1000)
return;
}
}
}
int main()
{
int i;
fin.getline(A, NM);
fin.getline(B, NM);
n=strlen(A);
m=strlen(B);
BuildPi();
KMP();
fout<<ori<<'\n';
for (i=1; i<=ori; i++)
{
fout<<V[i]<<" ";
}
return 0;
}