Cod sursa(job #2465230)

Utilizator lucian2015blaugranadevil lucian2015 Data 29 septembrie 2019 17:12:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
#define nmax 500001
using namespace std;


ifstream f("strmatch.in");
ofstream g("strmatch.out");

class Kmp{
private:
	int N, M;
	int pi[nmax + 5]; // prefix[i] = cel mai lung prefix pt s1 care este sufix pt s1(i) = primele i caractere
	int kmp[nmax + 5];
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++;
					kmp[nr] = i - N;
					k = pi[k];
				}

		}
		g << nr <<"\n";
		for ( int i = 1; i <= nr ; i++)
			g << kmp[i] <<" ";
	}


};


int main(){
	char a[nmax + 5], b[ nmax + 5];
	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);
	
}