Pagini recente » Cod sursa (job #2225691) | Cod sursa (job #1129435) | Cod sursa (job #1175586) | Cod sursa (job #1099435) | Cod sursa (job #2724863)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int LEN_MAX = 2e6 + 5;
const int ANS_MAX = 1e3;
char s1[LEN_MAX], s2[LEN_MAX];
int pi[LEN_MAX], len;
vector < int > Ans;
int main()
{
fin >> (s1 + 1) >> (s2 + 1);
for (int i = 2; s1[i]; i++)
{
while (len != 0 && s1[i] != s1[len + 1])
len = pi[len];
if (s1[i] == s1[len + 1])
len++;
pi[i] = len;
}
len = 0;
for (int i = 1; s2[i]; i++)
{
while (len != 0 && s1[len + 1] != s2[i])
len = pi[len];
if (s1[len + 1] == s2[i])
len++;
if (s1[len + 1] == 0)
{
if (Ans.size() <= ANS_MAX)
Ans.push_back(i - len);
len = pi[len];
}
}
fout << Ans.size() << "\n";
for (int i = 0; i < Ans.size(); i++)
fout << Ans[i] << " ";
return 0;
}