Cod sursa(job #1075287)

Utilizator rucarRucareanu Alexandru rucar Data 8 ianuarie 2014 20:14:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAXN 2000005
int m, i, n, nrsol;
int p[MAXN], sol[1001];
char s1[MAXN], s2[MAXN];

void prefix()
{
	int k = 0, i;
	for (i = 2; i <= m; i++)
	{
		while (k > 0 && s2[k + 1] != s2[i])
			k = p[k];
		if (s2[k + 1] == s2[i])
			k++;
		p[i] = k;
	}
}

void kmp()
{
	int i, k = 0;
	for (i = 1; i <= n; i++)
	{
		while (k > 0 && s2[k + 1] != s1[i])
			k = p[k];
		if (s2[k + 1] == s1[i])
			k++;
		if (k == m)
		{
			nrsol++;
			if (nrsol <= 1000)
				sol[nrsol] = i - m;
			k = p[m];
		}
	}
}

int main()
{
	FILE *f = fopen("strmatch.in", "r"), *g = fopen("strmatch.out", "w");
	fscanf(f,"%s%s", s2 + 1, s1 + 1);
	s2[0] = ' ';
	s1[0] = ' ';
	m = strlen(s2) - 1;
	n = strlen(s1) - 1;
	prefix(); 
	kmp();
	fprintf(g,"%d\n", nrsol);
	for (i = 1; i <= nrsol&&i <= 1000; i++)
		fprintf(g,"%d ", sol[i]);
	return 0;
}