Cod sursa(job #831725)

Utilizator radu.bRadu Brumariu radu.b Data 9 decembrie 2012 00:56:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
//
//  005.3.cc
//  005.1
//
//  Created by Radu Brumariu on 12/2/12.
//  Copyright (c) 2012 Radu Brumariu. All rights reserved.
//

#define MAXN 2000001

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>

int* compute_prefix(const char* P, int m);

int main(void) {

char* P = new char[MAXN];
char* T = new char[MAXN];

P[0] = T[0] = ' ';
  
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);

scanf("%s %s", (P+1), (T+1));
	
int n = strnlen(T+1, MAXN);
int m = strnlen(P+1, MAXN);

int* results = new int[MAXN];

if(m > n) {
  std::cout << "0" << std::endl;
  return 0;
}

int* pi = compute_prefix(P, m);

int q = 0;
int cnt = 0;
for (int i = 1; i <= n; i++) {
  while (q>0 && P[q+1] != T[i]) {
    q = pi[q];
	}
	if (P[q+1] == T[i]) {
		q++;
	}
	if (q == m) {
		q = pi[m];
    results[cnt++] = i-m;
	}
}
std::cout << cnt << std::endl;
for(int i = 0; (i < cnt && i < 1000); i++){
  std::cout << results[i] << " ";
}
std::cout << std::endl;

delete [] pi;
delete [] P;
delete [] T;
	
return 0;
}


int* compute_prefix(const char* P, int m){
	int *pi = new int[m+1];
  int k = 0;
  pi[1] = 0;
	for (int q = 2; q<=m; q++) {
		while (k>0 && P[k+1] != P[q]) {
			k = pi[k];
		}
		if (P[k+1] == P[q]) {
			k++;
		}
		pi[q] = k;
	}
	
	return pi;
}