Cod sursa(job #1245670)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 19 octombrie 2014 20:12:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <string.h>
#include <vector>
#define MAX 2000003

using namespace std;

int n, m;
char little[MAX], big[MAX];
vector<int> dp(MAX), ans;

void preprocess(){
	dp[0] = 0;
	for(int i = 1; i <= n; i++){
		if(dp[i-1] != i-1 && little[dp[i-1]] == little[i-1]){
			dp[i] = dp[i-1] + 1;
		}else{
			dp[i] = dp[i-1];
		}
	}
}

int main(){
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s%s", little, big);
	n = strlen(little);
	m = strlen(big);

	if(n > m){
		printf("0\n");
		return 0;
	}

	preprocess();

	int j = dp[0], i = 0;	// i - big string, j - little one
	while(i < m){
		if(little[j] == big[i]){
			if(j == n-1){
				j = dp[n];
				ans.push_back(i - n + 1);
			}else{
				j++;
			}
			i++;
		}else{
			if(j > 0){
				j = dp[j];
			}else{
				i++;
			}
		}
	}
	printf("%d\n", n = ans.size());
	for(int i = 0; i < n; i++){
		printf("%d ", ans[i]);
	}
	printf("\n");
	return 0;
}