Cod sursa(job #805725)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 31 octombrie 2012 23:34:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

const int N=2000002;

int pref[N];
string A,B;
vector <int> results;
int result;

class KMP{
	string A,B;
	int appereances;
	vector <int> appereances_positions;
	const int STR_MAX;
	int *fail;
public:
	KMP(string X,string Y,int maxString=2000100):STR_MAX(maxString){
		A=X;
		B=Y;
		fail=new int[STR_MAX];
		appereances=0;
		this->createFail();
		this->patternMatch();
	}
	bool createFail(){
		int failValue,i;
		fail[0]=fail[1]=0;
		for(i=2;i<=A.length();++i){
			failValue=fail[i-1];
			while(A[failValue]!=A[i-1] && failValue){
				failValue=fail[failValue];
			}
			if(A[failValue]==A[i-1]){
				fail[i]=failValue+1;
			}
		}
		return true;
	}
	bool patternMatch(){
		int i,currentstate=0;
		for(i=0;i<B.length();++i){
			if(B[i]==A[currentstate]){
				currentstate++;
			}
			else{
				while(A[currentstate]!=B[i] && currentstate){
					currentstate=fail[currentstate];
				}
				if(B[i]==A[currentstate]){
					currentstate++;
				}
			}
			if(currentstate==A.length()){
				currentstate=fail[currentstate];
				appereances++;
				appereances_positions.push_back(i-A.length()+1);
			}
		}
		return true;
	}
	int getApparitions(){
		return appereances;
	}
	vector<int> getAppPositions(){
		return appereances_positions;
	}
};

int main(){
	vector <int> results;
	vector <int>::iterator result;
	in>>A>>B;
	KMP algoritm(A,B);
	out<<algoritm.getApparitions()<<"\n";
	results=algoritm.getAppPositions();
	for(result=results.begin();result!=results.end();result++){
		out<<*result<<" ";
	}
	return 0;
}