Pagini recente » Cod sursa (job #400704) | Cod sursa (job #2771670) | Cod sursa (job #3235830) | Cod sursa (job #1169679) | Cod sursa (job #601290)
Cod sursa(job #601290)
#include <iostream>
#include <fstream>
#include <string>
#define NMax 2000005
using namespace std;
char N[NMax], M[NMax];
int n, m, pi[NMax], Match[NMax], NMatch;
void Read ()
{
ifstream fin ("strmatch.in");
fin >> N >> M;
n=strlen (N);
for (int i=n; i>0; --i)
{
N[i]=N[i-1];
}
N[0]='0';
m=strlen (M);
for (int i=m; i>0; --i)
{
M[i]=M[i-1];
}
M[0]='0';
fin.close ();
}
void Print ()
{
ofstream fout ("strmatch.out");
fout << NMatch << "\n";
for (int i=0; i<NMatch; ++i)
{
fout << Match[i] << " ";
}
fout << "\n";
fout.close ();
}
void CalculPrefix ()
{
int k=0;
pi[1]=0;
for (int i=2; i<=n; ++i)
{
while (k>0 and N[k+1]!=N[i])
{
k=pi[k];
}
if (N[k+1]==N[i])
{
k++;
}
pi[i]=k;
}
}
void KMP ()
{
int q=0;
CalculPrefix ();
for (int i=1; i<=m; ++i)
{
while (M[i]!=N[q+1] and q>0)
{
q=pi[q];
}
if (N[q+1]==M[i])
{
q++;
}
if (q==n)
{
Match[NMatch++]=i-n;
}
}
}
int main()
{
Read ();
KMP ();
Print ();
return 0;
}