Pagini recente » Cod sursa (job #2917303) | Cod sursa (job #2545571) | Cod sursa (job #2599838) | Cod sursa (job #711223) | Cod sursa (job #2937647)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int nmax = 2000005;
int lps[nmax];
int res[1005];
int ind = 0;
string pattern, text;
void calcKMP()
{
int l = 0;
lps[0] = 0;
int i = 1;
while (i < pattern.size())
{
if (pattern[l] == pattern[i])
{
lps[i++] = ++l;
}
else
{
if (l)
{
l = lps[l - 1];
}
else
{
lps[i++] = 0;
}
}
}
l = i = 0;
while ((text.size() - i) >= (pattern.size() - l))
{
if (pattern[l] == text[i])
{
i++;
l++;
}
if (l == pattern.size())
{
if (ind < 1000)
res[ind] = i - l;
ind++;
l = lps[l - 1];
}
else
{
if (i < text.size() && pattern[l] != text[i])
{
if (l)
l = lps[l - 1];
else
i++;
}
}
}
}
int main()
{
in >> pattern >> text;
calcKMP();
out << ind << '\n';
for (int i = 0; i < min(ind, 1000); i++)
{
out << res[i] << ' ';
}
}