Cod sursa(job #1246902)

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

using namespace std;

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

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

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;
}