Pagini recente » Cod sursa (job #260862) | Cod sursa (job #2410609) | Cod sursa (job #2678273) | Cod sursa (job #2545885) | Cod sursa (job #601293)
Cod sursa(job #601293)
#include <iostream>
#include <fstream>
#include <string>
#define NMax 2000005
using namespace std;
char N[NMax], M[NMax];
int n, m, pi[NMax], Match[1005], 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 ();
}
inline int Min (int a, int b)
{
if (a<b)
{
return a;
}
return b;
}
void Print ()
{
ofstream fout ("strmatch.out");
fout << NMatch << "\n";
for (int i=0; i<Min (NMatch, 1000); ++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)
{
if (NMatch<1000)
{
Match[NMatch++]=i-n;
}
else
{
NMatch++;
}
}
}
}
int main()
{
Read ();
KMP ();
Print ();
return 0;
}