Pagini recente » Cod sursa (job #2709901) | Cod sursa (job #2334795) | Cod sursa (job #2713140) | Cod sursa (job #1218958) | Cod sursa (job #2859805)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int kmp[4000004];
vector<int> place;
int main()
{
string s, t;
fin>>s>>t;
t = " " + s + t;
s = " " + s;
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;
k = 0;
for(int i = s.size();i < t.size(); i++)
{
while(k && s[k+1] != t[i])
k = kmp[k];
if(s[k+1] == t[i])
k++;
if(k == s.size() - 1)
{
ap++;
if (ap <= 1000)
place.push_back(i);
}
}
fout<<ap<<"\n";
for (auto a : place)
{
fout<<a - 2 * (s.size() - 1)<<" ";
}
return 0;
}