Cod sursa(job #2466286)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 1 octombrie 2019 20:32:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>

#include <string>

#include <cstring>

#include <vector>

using namespace std;









ifstream f("strmatch.in");

ofstream g("strmatch.out");

const int nmax = 2e6 + 5;

char a[nmax], b[nmax];

class Kmp{

private:

	int N, M;

	int pi[nmax];

	 // prefix[i] = cel mai lung prefix pt s1 care este sufix pt s1(i) = primele i caractere

	vector<int> kmp;

public:

	Kmp(int n, int m){

		N = n;

		M = m;

	}

	void prefix( char s1[] ){

		int k = 0;

		pi[1] = 0;

		for ( int i = 2 ; i <= N; i++ ){

			while( k != 0 && s1[k + 1] != s1[i] )

				k = pi[k];

			if( s1[k + 1] == s1[i])

				k++;

			pi[i] = k;



		}

	}

	void kmp1(char s2[], char s1[]){

		int k = 0, nr = 0;

		for( int i = 1; i <=M; i++ ){

				while( k != 0 && s1[k + 1] != s2[i] )

					k = pi[k];

				if( s1[k + 1] == s2[i] )

					k++;

				if( k == N ){

					nr++;

				if(kmp.size() < 1000)

					kmp.push_back(i - N);

					k = pi[k];

				}



		}

		g << nr <<"\n";

		    for(auto it : kmp)

		    	g << it<<" ";

	}





};





int main(){



	int n, m, i;

	f >> (a + 1)>> (b + 1);

	n = strlen(a + 1);

	m = strlen(b + 1);

	Kmp text(n , m);

	text.prefix(a);

	text.kmp1(b, a);



}