Pagini recente » Cod sursa (job #2432359) | Cod sursa (job #2730334) | Cod sursa (job #2783947) | Cod sursa (job #1287674) | Cod sursa (job #2870663)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
int n, na, k, pi[4000005], afis;
string a, b, s;
vector <int> v;
int main()
{
fin >> a >> b;
s = a + '$' + b;
n = s.size();
na = a.size();
for(int i = 1; i < n; i++)
{
k = pi[i - 1];
while(k > 0 && s[i] != s[k])
k = pi[k - 1];
if(s[i] == s[k])
k++;
pi[i] = k;
if(pi[i] == na)
{
afis++;
if(afis <= 1000)
v.push_back(i - 2 * na);
}
}
fout << afis << '\n';
for(int elem : v)
fout << elem << ' ';
return 0;
}