Pagini recente » Cod sursa (job #2953037) | Cod sursa (job #1117503) | Cod sursa (job #1475283) | Cod sursa (job #2021481) | Cod sursa (job #1243506)
#include <bits/stdc++.h>
using namespace std;
vector<int> Z_Algorithm( const string s )
{
const int N = s.size();
int L = 0, R = 0;
vector <int> z( N + 1, 0 );
for ( int i = 1; i < N; ++i )
{
if ( i <= R )
z[i] = min( R - i + 1, z[i - L] );
while ( i + z[i] < N && s[ z[i] ] == s[ i + z[i] ] ) z[i]++;
if ( R < i + z[i] - 1 )
{
L = i;
R = i + z[i] - 1;
}
}
return z;
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string P, T;
in >> P >> T;
vector <int> Z = Z_Algorithm( P + "#" + T );
vector <int> match;
for ( int i = P.size() + 1; i < Z.size(); ++i )
{
if ( Z[i] == P.size() )
match.push_back( i - P.size() - 1 );
}
out << match.size() << "\n";
for ( int i = 0; i < min( 1000, (int)match.size() ); ++i )
out << match[i] << " ";
return 0;
}