Pagini recente » Cod sursa (job #3162973) | Cod sursa (job #1412589) | Cod sursa (job #3230923) | Cod sursa (job #309052) | Cod sursa (job #2910638)
#include <fstream>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
const int max_size = 2e6;
int prefix[max_size], n, m;
vector <int> ans;
string a, b;
void kmp ()
{
int q = -1;
for (int i = 1; prefix[0] = 0, i < n; i++)
{
while (q >= 0 && a[q + 1] != a[i])
{
q = prefix[q];
}
if (a[q + 1] == a[i])
{
q++;
}
prefix[i] = q;
}
}
int main ()
{
long long rez = 0;
in >> a >> b;
n = a.size();
m = b.size();
kmp();
int q = -1;
for (int i = 0; i < m; i++)
{
while (q >= 0 && a[q + 1] != b[i])
{
q = prefix[q];
}
if (a[q + 1] == b[i])
{
q++;
}
if (q == n - 1)
{
q = prefix[n - 1];
rez++;
if (rez <= 1000)
{
ans.push_back(i - n + 1);
}
}
}
out << rez << '\n';
for (auto f : ans)
{
out << f << " " ;
}
in.close();
out.close();
return 0;
}