Cod sursa(job #914310)

Utilizator mucalmicmarcel almic mucalmic Data 14 martie 2013 00:58:12
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stdio.h>

#define MAX 2000000

using namespace std;

vector <int> pot, tab;

char smic[MAX], smare[MAX];

int main() {


freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, j, pos, lmi, lma, cand;
scanf("%s", smic);
scanf("%s", smare);

lmi = strlen(smic);
lma = strlen(smare);

tab.resize(lmi);
tab[0] = -1;

cand = -1;
    
for (i = 1; i < lmi; i++) {
	if (smic[i] == smic[cand+1]) {
		cand++;
		tab[i] = cand;
		
	}
	else {
		if (cand >= 0) {
			cand = tab[cand]; 
			i--;
			}
		else if (cand == -1) 
			tab[i] = -1;
	}		
	
		
}


j = 0;

for (i = 0; i < lma; i++) {	
	if (smic[j] == smare[i]) {
		j++;
		if (j == lmi) {
			pot.push_back(i-j+1);
			j = tab[j-1]+1;
		}
	}
	else 
		j = tab[j-1]+1;
}


printf("%d\n", pot.size());

int max = 1000;
if (max > pot.size())
	max = pot.size();
for (i = 0; i< pot.size(); i++) {
	printf("%d ",pot[i]);
}

printf("\n");
return 0;
}