Pagini recente » Cod sursa (job #2937884) | Cod sursa (job #225077) | Cod sursa (job #412560) | Cod sursa (job #187393) | Cod sursa (job #1969140)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int cnt;
vector<int> p, pos;
int N, M;
void Prefix( string& a );
void KMP();
int main()
{
fin >> a >> b;
N = a.size(), M = b.size();
p = vector<int>(N);
KMP();
fout << cnt << '\n';
for ( const int& x : pos )
fout << x << ' ';
fin.close();
fout.close();
return 0;
}
void Prefix( string& a )
{
int q{0};
for ( size_t i = 1; i < N; ++i )
{
while ( q > 0 && a[q] != a[i] )
q = p[q];
if ( a[q] == a[i] )
++q;
p[i] = q;
}
}
void KMP()
{
int q{0};
Prefix(a);
for ( size_t i = 0; i < M; ++i )
{
while ( q > 0 && a[q] != b[i] )
q = p[q - 1];
if ( a[q] == b[i] )
++q;
if ( q == N )
{
++cnt;
q = p[q - 1];
if ( cnt <= 1000 )
pos.push_back(i + 1 - a.size());
}
}
}