Cod sursa(job #606246)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 3 august 2011 18:19:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <iostream>
#include <string>

using namespace std;

int N;
int occurrences[1001];

void CreateTable(const char *W, int *T, const int lenW)
{	
	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++;
		}
	}*/
	int k = -1, i;
	for (i = 1; i < lenW; i++)
	{
		while (k >= 0 && W[k + 1] != W[i])
			k = T[k];
		if (W[k + 1] == W[i])
			k++;
		T[i] = k;
	}
}

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)
			{	
				if (N<1000)
					occurrences[N] = m;
				
				N++;
				m++;
				i=0;
				continue;
			}
			i++;
		}
		else
		{
			m = m + i - T[i];
			
			if (T[i] > -1)
				i = T[i];
			else
				i = 0;
		}
	}*/
	
	int k = -1;

	for (i = 0; i < lenS; i++) 
	{
		while (k >= 0 && W[k + 1] != S[i])
			k = T[k];

		if (W[k + 1] == S[i])
			k++;

		if (k == lenW - 1)
		{
			if (N<1000)
				occurrences[N++] = i - lenW + 1;
			else
				N++;
		}
	}
	
	return lenS;
}

int main()
{
	int pos = -1, oldpos = 0, lenS, lenW;
	int *T;
	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());
	
	KMP(S.c_str(), W.c_str(), T, lenS, lenW);
	
	fout << N << endl;

	for (int i=0; i< ((N<=1000)?N:1000); ++i)
		fout << occurrences[i] << " ";
	fout << endl;

	delete T;

	return 0;
}