Pagini recente » Profil Clelia | Cod sursa (job #1173061) | w2 | Cod sursa (job #1685931) | Cod sursa (job #2145762)
#include <fstream>
#include <string>
#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;
i = j = len = 0;
preLps ( pat, len, lps );
//for ( auto it = lps.begin(); it != lps.end(); ++it )
// fout << *it << " ";
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()
{
getline ( fin, pat ), getline ( fin, txt );
//fout << pat << '\n' << txt;
kmp ( pat, txt );
fout << sol.size() << '\n';
for ( auto it = sol.begin(); it != sol.end(); ++it )
fout << *it << " ";
}