Cod sursa(job #3230173)

Utilizator iusty64Iustin Epanu iusty64 Data 19 mai 2024 18:05:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

const int Vmax = 2000001;

int n, m, sol[Vmax], pi[Vmax];

char a[Vmax], b[Vmax];

void Pi(){
	int k = 0;
	pi[1] = 0;
	for(int i = 2; i <= n; i++){
		while(k && a[k+1] != a[i]){
			k = pi[k];
		}
		if(a[k+1] == a[i]){
			++k;
		}
		pi[i] = k;
	}
}

int main(){
  freopen("strmatch.in", "r", stdin);
  freopen("strmatch.out", "w", stdout);
	scanf("%s%s", (a + 1), (b + 1));
	n = strlen(a + 1);
	m = strlen(b + 1);
	Pi();
	int k = 0;
	for(int i = 1; i <= m; i++){
		while(k && a[k+1] != b[i]){
			k = pi[k];
		}
		if(a[k+1] == b[i]){
			++k;
		}
		if(k == n)
			sol[++sol[0]] = i - n;
	}
	printf("%d\n", sol[0]);
	for(int i = 1; i <= sol[0] && i <= 1000; i++){
		printf("%d ", sol[i]);
	}
	return 0;
}