Cod sursa(job #2354734)

Utilizator FlorianMarcuMarcu Florian Cristian FlorianMarcu Data 25 februarie 2019 15:35:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
//#include "pch.h"
#include <iostream>
#include <fstream>	
#include <cstring>
#include <algorithm>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int pi[2000005];
char A[2000005], B[2000005];
int n, m;

void prefix()       //CALCUL FUNCTIE PREFIX
{
	
	int k = 0;
	pi[1] = 0;
	for (int i = 2; i <= n; i++) {
		
		while (k > 0 and A[k + 1] != A[i])

			k = pi[k];
		if (A[k + 1] == A[i])
			k++;

		pi[i] = k;
	}
}
int main()
{
	fin.getline(A+1,2000005);
	fin.getline(B+1,2000005); cout << A << B;
	n = strlen(A+ 1) ; m = strlen(B+ 1) ;
	int v[2000];
	int NR = 0;
	
	prefix();
	
	//               POTRIVIRE KMP
	int q = 0;
	for (int i = 1; i <= m; i++) {
		while (q > 0 and A[q + 1] != B[i])
			q = pi[q];
		if (A[q + 1] == B[i])
			q++;
		if (q == n) 
			if(n<=1000)
				v[++NR] = i - n;
			else ++NR;
			
	}

	fout << NR <<"\n";
	for (int i = 1; i <= min(NR, 1000); i++)
		fout << v[i]<<" ";

}