Pagini recente » Cod sursa (job #3232543) | Cod sursa (job #2458059) | Cod sursa (job #1732921) | Cod sursa (job #2889974) | Cod sursa (job #1755900)
#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, nr;
string a, b;
void Prefix();
void KMP();
int main()
{
getline(fin, a);
getline(fin, b);
Prefix();
KMP();
nr = ans.size();
fout << nr << '\n';
for ( int i = 0; i < nr && i < 1000; i++)
fout << ans[i] << ' ';
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);
}
}