Pagini recente » Cod sursa (job #770645) | Cod sursa (job #828873) | Cod sursa (job #428839) | Cod sursa (job #1276731) | Cod sursa (job #1830958)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char a[2000001],b[2000001];
int s[2000001];
int n,m;
void Citire ()
{
ifstream f ("strmatch.in");
f>>a;
f>>b;
n=strlen(b);
m=strlen(a);
}
void Prefix_Sufix ()
{
int i=1,j=0;
while (i<m)
{
if (a[j]==a[i])
{
s[i]=j+1;
j++;
}
else
{
while (j!=0)
{
j=s[j-1];
if (a[j]==a[i])
{
s[i]=j+1;
j++;
}
}
}
i++;
}
}
void KMP ()
{
ofstream g("strmatch.out");
int i=0,j=0,nra=0,k=0;
int p[20000];
while (i<n)
{
if (b[i]==a[j])
{
j++;
if (j==m)
{
nra++;
p[k++]=i-m+1;
j=s[j-1];
}
}
else
{
if (j!=0)
j=s[j-1];
}
i++;
}
g<<nra<<endl;
for (int i=0;i<k;i++)
g<<p[i]<<" ";
}
int main()
{
Citire ();
Prefix_Sufix();
KMP ();
return 0;
}