Pagini recente » Cod sursa (job #2615378) | Cod sursa (job #1155675) | Cod sursa (job #2229838) | Profil Harabula (rEbyTer) Adrian | Cod sursa (job #2145719)
#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 << " ";
}