Pagini recente » Cod sursa (job #887010) | Cod sursa (job #338475) | Cod sursa (job #1552311) | Cod sursa (job #423377) | Cod sursa (job #1969136)
#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;
void Prefix( string& a );
void KMP();
int main()
{
fin >> a >> b;
p = vector<int>(a.size());
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 < a.size(); ++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 < b.size(); ++i )
{
while ( q > 0 && a[q] != b[i] )
q = p[q - 1];
if ( a[q] == b[i] )
++q;
if ( q == a.size() )
{
++cnt;
q = p[q - 1];
if ( pos.size() < 1000 )
pos.push_back(i + 1 - a.size());
}
}
}