Cod sursa(job #1219995)

Utilizator ptquake10ptquake10 ptquake10 Data 16 august 2014 11:51:29
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int last[2000010], nr;
vector<int> sol;
string a, b;

void pref() {
	int k = 0;
	last[1] = 0;
	for (int i = 2; i < a.length(); i++) {
		while (k > 0 && a[k+1] != a[i]) k = last[k];
		if (a[k+1] == a[i]) k++;
		last[i] = k;
	}	
}

void kmp() {
	int k = 0;
	for (int i = 1; i < b.length(); i++) {
		while (k > 0 && a[k+1] != b[i]) k = last[k];
		if (a[k+1] == b[i]) {
			k++;
			if (k == a.length() - 1) {
				nr++;
				if (nr <= 1000) {
					sol.push_back(i - a.length() + 1);
				}
				k = last[k];
			}
		} else {
			k = last[k];
		}
	}
}

int main() {
	int x, y;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	cin >> a;
	cin >> b;
	a = " " + a;
	b = " " + b;
	pref();
	kmp();
	
	printf("%d\n", nr);
	for (int i = 0; i < sol.size(); i++) {
		printf("%d ", sol[i]);
	}
	
	return 0;
}