Cod sursa(job #1830980)
Utilizator | Data | 17 decembrie 2016 11:59:08 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 16 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.26 kb |
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
char a[2000001],b[2000001];
int s[2000001];
int p[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;
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<1000;i++)
g<<p[i]<<" ";
}
int main()
{
Citire ();
Prefix_Sufix();
KMP ();
return 0;
}