Cod sursa(job #606186)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 3 august 2011 15:53:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

void CreateTable(const char *W, int *T, const int lenW)
{
	int pos = 2;
	int cnd = 0;
	
	T[0] = -1;
	T[1] = 0;
	
	while (pos < lenW)
	{
		if (W[pos-1] == W[cnd])
		{
			cnd++;
			T[pos] = cnd;
			pos++;
		}
		else if (cnd > 0)
		{
			cnd = T[cnd];
		}
		else
		{
			T[pos] = 0;
			pos++;
		}
	}
}

inline int KMP(const char *S, const char *W, const int *T, const int lenS, const int lenW)
{
	int m = 0;
	int i = 0;
	
	while (m+i < lenS)
	{
		if (S[m+i] == W[i])
		{
			if (i == lenW-1)
				return m;
			i++;
		}
		else
		{
			m = m + i - T[i];
			
			if (T[i] > -1)
				i = T[i];
			else
				i = 0;
		}
	}
	
	return lenS;
}

int main()
{
	int n = 0, pos = -1, oldpos = 0, lenS, lenW;
	int *T, occurrences[1001];
	fstream fin("strmatch.in", fstream::in);
	fstream fout("strmatch.out", fstream::out);

	string S;
	string W;

	fin >> W;
	fin >> S;
	
	fin.close();
	
	lenS = S.length();
	lenW = W.length();
	
	//cout << W << " " << W.length() << endl;
	//cout << S << " " << S.length() << endl;
	
	T = new int[W.length()+2];
	
	CreateTable(W.c_str(), T, W.length());

	do
	{
		oldpos = pos + oldpos + 1;
		pos = KMP(S.c_str()+oldpos, W.c_str(), T, lenS - oldpos + 1, lenW);
		
		if (pos + oldpos >= S.length())
			break;

		occurrences[n] = pos + oldpos;
		n++;
	} while (n<1000);
	
	fout << n << endl;

	for (int i=0; i<n; ++i)
		fout << occurrences[i] << " ";
	fout << endl;

	delete T;

	return 0;
}