Cod sursa(job #679259)

Utilizator cpblncCristian Grajdeanu cpblnc Data 12 februarie 2012 22:34:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int match(string s, string w, vector<int> t, vector<int>& res){
	int m = 0;
	int i = 0;
	int counter = 0;
	while(m+i < s.size()){
		if(w[i] == s[m+i]){
			if(i == w.size()-1) {
				counter++;
				res.push_back(m);
				i = 0; 
				m++;
			} else {
				i++;
			}
		} else {
			m = m + i - t[i];
			if(t[i] > -1)
				i = t[i];
			else
				i = 0;
		}
	}
	
	return counter;
}

vector<int> createKMPTable(string str){
	vector<int> table;
	if(str.size() == 0)
		return table;
	table.push_back(-1);
	if(str.size() == 1) {
		return table;
	}
	table.push_back(0);
	if(str.size() == 2) {
		return table;
	}
	int i = 2;
	int cnd = 0;
	
	while( i <  str.size() ) {
		if(str[i-1] == str[cnd]){
			table.push_back(++cnd);
			i++;
		} else if(cnd > 0){
			cnd = table[cnd];
		} else {
			table.push_back(0);
			i++;
		}
	}
	return table;
}

int main(int argc, char** argv){
	//variables
	string w, s;
	ifstream in;
	
	//read
	in.open("strmatch.in");
	in >> w;
	in >> s;
	in.close();
	
	//solve
	int res = 0;
	vector<int> matchVec;
	
	vector<int> tKMP = createKMPTable(w);
	
	if(w.size() < = s.size()) {
		/*for(int i = 0; i < tKMP.size(); i++){
			cout << tKMP[i];
		}
		cout << "\n";*/
		res = match(s, w, tKMP, matchVec);
	} 
	
	//write
	ofstream out;
	out.open("strmatch.out");
	out << res << "\n";
	for(int i = 0; i < matchVec.size(); i++){
		out << matchVec[i] << " ";
	}
	out.close();
}