Cod sursa(job #1044675)

Utilizator L.DanielLungu Daniel L.Daniel Data 30 noiembrie 2013 11:12:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <string.h>
using namespace std;
char a[2000005], b[2000005];
int pi[2000005], c[2000005], s;
void prefix()
{
int n, i, k;
n = strlen(a)-1;
pi[1] = 0;
k = 0;
for (i = 2; i <= n; i++)
{
while (k > 0 && a[k + 1] != a[i])
k = pi[k];
if (a[k + 1] == a[i])k++;
pi[i] = k;
}
}
void KMP()
{
int n, m, q, i;
n = strlen(a)-1;
m = strlen(b)-1;
q = 0;
for (i = 1; i <= m; i++)
{
while (q > 0 && a[q + 1] != b[i])
q = pi[q];
if (a[q + 1] == b[i])q++;
if (q == n)
{
s++;
c[s] = i - n;
}
}
}
int main()
{
	int i;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(a, 2000005, '\n');
	f.getline(b, 2000005, '\n');
	for (i = strlen(a); i >= 0; i--)a[i] = a[i - 1];
	for (i = strlen(b); i >= 0; i--)b[i] = b[i - 1];
	a[0] =' ';
	b[0] =' ';
prefix();
KMP();
g << s << endl;
for ( i = 1; i <= s; i++)
g<< c[i] << " ";
	return 0;
}