Cod sursa(job #2145719)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 27 februarie 2018 16:11:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <vector>

typedef unsigned int uint;
using namespace std;

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

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;

	preLps ( pat, len, lps );

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

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

int main()
{
	fin >> pat >> txt;

	kmp ( pat, txt );

	fout << sol.size() << '\n';

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