Cod sursa(job #644652)

Utilizator Antonius74Antonius Cezar Hegyes Antonius74 Data 7 decembrie 2011 11:21:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>
#include <string>
using namespace std;
#define NMAX 200000

void kmp_table(char[], int[]);

int main()
{
	ifstream indata;
	indata.open("strmatch.in");
	ofstream outdata;
	outdata.open("strmatch.out");
	
	vector <int> pozitii;
	char a[NMAX], b[NMAX];
	
	indata.getline(b, NMAX);
	indata.getline(a, NMAX);
	
	int T[strlen(b)];
	kmp_table(b, T);

	int m = 0, i = 0;
	while (i + m < strlen(a))
		if (b[i] == a[m + i])
			if (i == strlen(b) - 1)
			{
				pozitii.push_back(m);
				m += i - T[i];
				i = (T[i] > -1) ? T[i] : 0;
			}
			else
				i++;
		else
		{
			m += i - T[i];
			i = (T[i] > -1) ? T[i] : 0;
		}
		
	outdata<<pozitii.size()<<"\n";
	for (int i = 0; i < pozitii.size(); i++)
		outdata<<pozitii[i]<<" ";
}

void kmp_table(char b[], int T[])
{
	int pos = 2, cnd = T[1] = 0;
	T[0] = -1;
	
	while (pos < strlen(b))
		if (b[pos - 1] == b[cnd])
			T[pos++] = ++cnd;
		else 
			if (cnd > 0)
				cnd = T[cnd];
			else
				T[pos++] = 0;			
}