Pagini recente » Cod sursa (job #2955641) | Cod sursa (job #2145725) | Cod sursa (job #1930728) | Cod sursa (job #1684724) | Cod sursa (job #3263569)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
int a_len, s_len, pi[4000005], afis;
vector <int> ans;
string a, b, s;
int main()
{
fin >> a >> b;
s = '$' + a + '$' + b;
a_len = a.size();
s_len = s.size();
for(int i = 2; i < s_len; i++)
{
int k = pi[i - 1];
while(k && s[i] != s[k + 1])
k = pi[k];
if(s[i] == s[k + 1])
k++;
pi[i] = k;
if(k == a_len)
{
afis++;
if(afis <= 1000)
ans.push_back(i - 2 * a_len - 1);
}
}
fout << afis << '\n';
for(int x : ans)
fout << x << ' ';
return 0;
}