Pagini recente » Cod sursa (job #1756496) | Cod sursa (job #220277) | Cod sursa (job #270418) | Cod sursa (job #2321182) | Cod sursa (job #1216338)
#include <bits/stdc++.h>
using namespace std;
vector<int> Z_Algorithm( const string &str )
{
int L = 0, R = 0;
int lg = str.size();
vector <int> Z( lg + 1, 0 );
for ( int i = 1; i < lg; ++i )
{
if ( i > R )
{
L = R = i;
while ( R < lg && str[R - L] == str[R] ) R++;
R--;
Z[i] = R - L + 1;
}
else
{
int p = i - L;
if ( Z[p] < R - i + 1 )
Z[i] = Z[p];
else
{
L = i;
while ( R < lg && str[R - L] == str[R] ) R++;
R--;
Z[i] = R - L + 1;
}
}
}
return Z;
}
string P, T;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> P >> T;
vector <int> Z = Z_Algorithm( P + T );
vector <int> match;
for ( int i = P.size(); i < T.size(); ++i )
{
if ( Z[i] == P.size() )
match.push_back( i - P.size() );
}
out << match.size() << "\n";
for ( int i = 0; i < min( 1000, (int)match.size() ); ++i )
out << match[i] << " ";
return 0;
}