Cod sursa(job #1349231)

Utilizator cristian.enciuCristian Enciu cristian.enciu Data 20 februarie 2015 02:04:16
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>

int t[2000010];

using namespace std;

int main()
{
	string pat;
	string s;

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

	t[0] = -1;
	t[1] = 0;

	int i, j, n;

	cin >> pat;
	cin >> s;

	n = pat.length();
	i = 2; j = 0;
	while(i < n) {
		if(pat[i-1] == pat[j]) {
			++j;
			t[i] = j;
			++i;
		} else if(j > 0) {
			j = t[j];
		} else {
			t[i] = 0;
			++i;
		}

		++i;
	}

	int m = s.length();
	vector<int> lame;
	i = 0;
	j = 0;
	while(i + j < m) {
		if(s[i + j] == pat[j]) {
			if(j == n - 1) {
				lame.push_back(i);
				i += j - t[j];
				j = t[j];
			}
			++j;
		} else {
			if(t[j] > -1) {
				i += j - t[j];
				j = t[j];
			} else {
				j = 0;
				++i;
			}
		}
	}

	printf("%d\n", lame.size());
	for(int i = 0 ; i < lame.size() ; ++i) {
		printf("%d ", lame[i]);
	}

	return 0;
}