Cod sursa(job #796947)

Utilizator noctavianNastasie Ion Octavian noctavian Data 13 octombrie 2012 00:33:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

void compute_t(string W, int T[]) {
	int cnd = 0;
	int pos = 2;
	T[0] = -1;
	T[1] = 0;

	while(pos < 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++;
		}
	}
}

int main() {
	ifstream in("strmatch.in");
	string A, B;
	in >> A >> B;
	in.close();

	int T[A.length()];
	compute_t(A, T);

	int n = 0, poz[1000];
	int m = 0, i = 0;

	while(m+i < B.length()) {
		if(A[i] == B[m+i]) {
			if(i == A.length() - 1) {
				n++;
				if(n <= 1000)
					poz[n-1] = m;						
				m = m + i - T[i];
				i = T[i] > -1 ? T[i] : 0;
			}
			else
				i++;
		} else {
			m = m + i - T[i];
			i = T[i] > -1 ? T[i] : 0;
		}
	}

	ofstream out("strmatch.out");
	out << n << endl;
	int val = n < 1000 ? n: 1000;
	for(i = 0; i < val; i++)
		out << poz[i] << " ";
	out.close();
	return 0;
}