Cod sursa(job #3230151)

Utilizator iusty64Iustin Epanu iusty64 Data 19 mai 2024 14:53:30
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <cstring>
using namespace std;

const int Vmax = 2000001;

int n, m, sol[1001], 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(){
  ifstream fin("strmatch.in");
  ofstream fout("strmatch.out");
	fin >> a >> b;
	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;
	}
	fout<<sol[0]<<'\n';
	for(int i = 1; i <= sol[0] && i <= 1000; i++){
		fout<<sol[i]<<" ";
	}
	return 0;
}