Cod sursa(job #2465237)

Utilizator lucian2015blaugranadevil lucian2015 Data 29 septembrie 2019 17:21:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 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);
	
}