Pagini recente » Cod sursa (job #1342372) | Cod sursa (job #798469) | Cod sursa (job #1773375) | Cod sursa (job #553973) | Cod sursa (job #1755889)
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> ans, p;
int n, m;
string a, b;
void Prefix();
void KMP();
int main()
{
getline(fin, a);
getline(fin, b);
Prefix();
KMP();
fout << ans.size() << '\n';
for ( auto x : ans )
fout << x << ' ';
fin.close();
fout.close();
return 0;
}
void Prefix()
{
int k = 0;
n = a.size();
p = vector<int>(n + 1);
for ( int i = 1; i < n; ++i )
{
while ( k > 0 && a[k] != a[i] )
k = p[k - 1];
if ( a[i] == a[k] )
k++;
p[i] = k;
}
}
void KMP()
{
int k = 0;
m = b.size();
for (int i = 0; i < m; ++i)
{
while( k > 0 && b[i] != a[k] )
k = p[k - 1];
if ( b[i] == a[k] )
++k;
if (k == n)
ans.push_back(i - n + 1);
if ( ans.size() == 1000 )
return;
}
}