Cod sursa(job #940826)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 17 aprilie 2013 10:03:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#include <cstring>

#define N_MAX (1<<21)

char P[N_MAX], T[N_MAX];
int Pi[N_MAX], Sol[N_MAX];
int N, M;

void Prefix_Function (char *P) {
	M = strlen(P + 1) - 1;
	int k = 0;
	Pi[1] = 0;

	for (int i = 2; i <= M; ++i) {
		while (k > 0 && P[i] != P[k+1])
			k = Pi[k];
		if (P[i] == P[k + 1])
			++k;
		Pi[i] = k;
	}
}

void KMP_String_Match (char *P, char *T) {
	M = strlen(P + 1) - 1;
	N = strlen(T + 1) - 1;
	int k = 0;

	for (int i = 1; i <= N; ++i) {
		while (k > 0 && T[i] != P[k+1])
			k = Pi[k];

		if (T[i] == P[k+1])
			++k;
		if (k == M) {
			Sol[++Sol[0]] = i - M;
			k = Pi[k];
		}
	}
}

int main() {
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
  
  fgets(P + 1, N_MAX, stdin);
  fgets(T + 1, N_MAX, stdin);
  
  Prefix_Function (P);
  KMP_String_Match (P, T);  

  printf ("%d\n", Sol[0]);
  for (int i = 1; i <= Sol[0]; ++i)
  	if (i <= 1000)
  		printf ("%d ", Sol[i]);

  return 0;
}