Pagini recente » Borderou de evaluare (job #1438101) | Borderou de evaluare (job #3217931) | Borderou de evaluare (job #1429382) | Borderou de evaluare (job #2305893) | Cod sursa (job #2145778)
#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 << " ";
}