Cod sursa(job #3230153)

Utilizator iusty64Iustin Epanu iusty64 Data 19 mai 2024 14:58:26
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#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(){
  ifstream fin("strmatch.in");
  ofstream fout("strmatch.out");
	fin >> (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;
	}
	fout<<sol[0]<<'\n';
	for(int i = 1; i <= sol[0] && i <= 1000; i++){
		fout<<sol[i]<<" ";
	}
	return 0;
}