Cod sursa(job #1349264)

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

int t[2000010];
char pat[2000010];
char s[2000010];
using namespace std;

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

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

	int i, j, n;

	scanf("%s", pat);
	scanf("%s", s);

	n = strlen(pat);
	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;
		}
	}

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

	printf("%d\n", kkt);
	kkt = kkt > 1000 ? 1000 : kkt;
	for(i = 0 ; i < kkt ; ++i) {
		printf("%d ", lame[i]);
	}

	return 0;
}