Cod sursa(job #2145778)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 27 februarie 2018 16:48:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <string>
#include <vector>

typedef unsigned int uint;
using namespace std;

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

uint maxSize;
string pat,txt;
vector <uint> sol;

/// lps = longest prefix suffix
void preLps ( string pat, uint &i, vector <uint> &lps )
{
	lps.push_back (0);
	uint prev = 0;
	i = 1;

	while ( pat[i] )
	{
		if ( pat[i] == pat[prev] )
			lps.push_back(++prev), ++i;
		else
		{
			if ( prev )
				prev = lps[prev - 1];
			else
				lps.push_back (0), ++i;
		}
	}
}

void kmp ( string pat, string txt )
{
	uint i,j,len;
	vector <uint> lps;

	i = j = len = 0;

	preLps ( pat, len, lps );

	while ( txt[i] )
	{
		if ( txt[i] == pat[j] )
		{
			++i, ++j;

			if ( j == len )
			{
				j = lps[j - 1];

				++maxSize;

				if ( maxSize <= 1000 )
					sol.push_back ( i - len );
			}
		}
		else
		{
			if ( j )
				j = lps[j - 1];
			else
				++i;
		}
	}
}

int main()
{
	getline ( fin, pat ), getline ( fin, txt );

	kmp ( pat, txt );

	fout << maxSize << '\n';

	for ( auto it = sol.begin(); it != sol.end(); ++it )
		fout << *it << " ";
}