Cod sursa(job #1028441)

Utilizator FoaiaFoaia de Hartie Foaia Data 14 noiembrie 2013 06:13:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
	
#include <stdio.h>
#include <string.h>
#define mx 2000010
long pi[mx+1];
long v[1024];
char s1[mx+2],s2[mx+2];

 int prefix(const char *s) {
	int k = 0, i = 0;
	
	const char *start = s;
	
	for (i = 2, s += 2; *s; i++, s++) {
		for (; k && !(start[k + 1] == *s); k = pi[k]);
		if (start[k + 1] == *s)
			k++;
			
		pi[i] = k;
	}
	
	return i - 2;
}

int h, i;

void kmp(const char *s, const char *f) {
	int n = prefix(--s);
	
	int k = 0, i = 0;
	for (i = 0; *f; i++, f++) {
		for (; k && !(s[k + 1] == *f); k = pi[k]);
		if (s[k + 1] == *f)
			k++;
			
		if (k == n) {
                        h++;
                        k = pi[k];
                        if (h<=1000)
                                v[h]=i-n + 1;
                }
        }
}
 
int main(void)
{
     
      freopen("strmatch.in","r",stdin);
        freopen("strmatch.out","w",stdout);    fgets(s1,mx,stdin);
        fgets(s2,mx,stdin);
        kmp(s1, s2);
        printf("%ld\n",h);
        if (h>1000)
                h=1000;
        for (i=1; i<=h; i++)
                printf("%ld ",v[i]);
        fclose(stdin);
        fclose(stdout);
        return 0;
}