Cod sursa(job #1248021)

Utilizator adysnookAdrian Munteanu adysnook Data 24 octombrie 2014 14:47:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

int main(){
	string W, S;
	vector<int> T;
	getline(in, W);
	getline(in, S);
	T.resize(W.length());
	if (T.size()>1)
	{   //kmp table
		int pos = 2, cnd = 0;
		T[0] = -1;
		T[1] = 0;
		while (pos < (int)W.length()){
			if (W[pos - 1] == W[cnd]){
				++cnd;
				T[pos] = cnd;
				++pos;
			}
			else if (cnd > 0){
				cnd = T[cnd];
			}
			else{
				T[pos] = 0;
				++pos;
			}
		}
	}
	else{
		T[0] = -1;
	}
	vector<int> matches;
	int m = 0, i = 0;
	while (m + i < (int)S.length()){
		if (W[i] == S[m + i]){
			if (i == (int)W.length() - 1){
				matches.push_back(m);
				if (T[i] > -1){
					m = m + i - T[i];
					i = T[i];
				}
				else{
					i = 0;
					++m;
				}
				continue;
			}
			++i;
		}
		else{
			if (T[i] > -1){
				m = m + i - T[i];
				i = T[i];
			}
			else{
				i = 0;
				++m;
			}
		}

	}
	out << matches.size() << "\n";
	for (i = 0; i < min((int)matches.size(), 1000); ++i){
		out << matches[i] << " ";
	}

	return 0;
}