Cod sursa(job #2019036)

Utilizator bcrisBianca Cristina bcris Data 6 septembrie 2017 18:24:52
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <stdio.h>
#include <vector>
#include <cstdio>
#include <string.h>

using namespace std;

#define NMAX 2000000

int table[NMAX];
char A[NMAX], B[NMAX];
vector<int> solutions;

// void make_table(string A) {
// 	table[1] = 0;
// 	int j = 0, i = 0;

// 	len = strlen(A);

// 	while (i < len && j < len) {
// 		if (A[i] == A[j]) {
// 			table[i] = table[j] + 1;
// 			i++;
// 			j++;
// 		} else {
// 			j = table[j - 1];
// 			if (A[j] != A[i]) {
// 				table[i] = table[j];
// 				i++;
// 			}
// 		}
// 	} 
// }

void make_prefix() {
	int i;
	int j = 0;
 	int M = strlen(A);

	for (i = 1; i < M; i++) {
		while (j && A[j] != A[i])
			j = table[j];
		if (A[j] == A[i])
			j++;
		table[i] = j;
	}	

}

void search() {
	int i = 0, m = 0;
	int N = strlen(B);
	int M = strlen(A);

	while(m + i < N) {
		if (A[i] == B[m + i]) {
			i++;
			if (i == M) {
				solutions.push_back(m);
				m = m + i - table[i-1];
				i = table[i-1];
			}
		} else {
			if (i > 0) {
				if (table[i-1] > 0) {
					m = m + i - table[i-1];
					i = table[i];
				} else {
					m = m + i + 1 - table[i-1];
					i = 0;
				}	
			} else {
				m = m + i + 1;
				i = 0;
			}	
		}
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	
	scanf("%s\n", A);
	scanf("%s\n", B);

	make_prefix();
	search();

	int s = solutions.size();
	printf("%d\n", s);
	int printed = 0;
	for (std::vector<int>::iterator it = solutions.begin(); it != solutions.end() && printed < 1000; ++it) {
		printf("%d ", *it);
		printed++;
	}


	return 0;
}