Pagini recente » Cod sursa (job #2430996) | Cod sursa (job #1492455) | Cod sursa (job #367269) | Cod sursa (job #862240) | Cod sursa (job #1368459)
#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] == A.size() )
match.push_back(i - A.size() - 1);
out << match.size() << "\n";
for (int i = 0; i < min(1000, (int)match.size()); ++i)
out << match[i] << " ";
return 0;
}