Pagini recente » Cod sursa (job #2726246) | Cod sursa (job #2063392) | Cod sursa (job #1803713) | Cod sursa (job #1606889) | Cod sursa (job #2857497)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
int kmp[2000000];
int main() {
string s, t;
in >> s >> t;
t = " " + s + t;
int n = t.size() - 1;
int k = 0;
kmp[1] = 0;
for (int i = 2; i <= n; i++)
{
while (k > 0 && t[k + 1] != t[i])
{
k = kmp[k];
}
if (t[k + 1] == t[i]) k++;
kmp[i] = k;
}
int ap = 0;
vector<int> place;
for (int i = s.size(); i <= n; i++)
{
if (kmp[i] == s.size()){
ap++;
if (ap <= 1000)
place.push_back(i);
}
}
out << ap << '\n';
for (auto a : place)
{
out << a - 2 * s.size() << ' ';
}
return 0;
}