Pagini recente » Cod sursa (job #2451132) | Cod sursa (job #3224231) | Cod sursa (job #1878885) | Istoria paginii runda/vot/voteaza_algorel/clasament | Cod sursa (job #1830961)
#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[200000];
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;
}