Pagini recente » Cod sursa (job #357441) | Cod sursa (job #1229365) | Cod sursa (job #147650) | Cod sursa (job #2714613) | Cod sursa (job #1368449)
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 2000000;
vector<int> Z_Algorithm(const string& str)
{
const int N = static_cast<int>(str.size());
vector<int> Z(N, 0);
int L = 0, R = 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 && str[ Z[i] ] == str[ i + Z[i] ] ) Z[i]++;
if ( i + Z[i] - 1 > R )
{
L = i;
R = i + Z[i] - 1;
}
}
return Z;
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string A, B;
in >> A >> B;
vector<int> Z = Z_Algorithm(A + "$" + B);
vector<int> match;
for (size_t i = 0; i < Z.size(); ++i )
if ( Z[i] == B.size() )
match.push_back(i - B.size() - 1);
out << match.size() << "\n";
for (int i = 0; i < min(1000, (int)match.size()); ++i)
out << match[i] << " ";
return 0;
}