Cod sursa(job #1908085)

Utilizator tonisnakesBoar Antonio tonisnakes Data 6 martie 2017 22:37:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000005
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

char a[NMAX], b[NMAX];
int n, m, pi[NMAX];
vector <int> matches;

int main ()
{
	fin.getline(a + 1,NMAX);
	n = strlen(a + 1);
	fin.getline(b + 1,NMAX);
	m = strlen(b + 1);
	int k = 0;
	for (int i = 2; i <= n; ++i) {
		while (k != 0 && a[k+1] != a[i]) {
			k = pi[k];
		}
		if (a[k+1] == a[i]) {
			++k;
		}
		pi[i] = k;
	}
	k = 0;
	for (int i = 1; i <= m; ++i) {
		while (k != 0 && a[k+1] != b[i]) {
			k = pi[k];
		}
		if (a[k+1] == b[i]) {
			++k;
		}
		if (k == n) {
			matches.push_back(i - n);
			k = pi[k];
		}
	}
	fout << matches.size() << '\n';
	for (int i = 0; i < min(1000, int(matches.size())); ++i) {
		fout << matches[i] << " ";
	}
	
	fin.close();
	fout.close();
	return 0;
}