Pagini recente » Cod sursa (job #3362382) | Cod sursa (job #3362732) | Cod sursa (job #3361473) | Cod sursa (job #3362857) | Cod sursa (job #3362380)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
string a, b;
int z[2000005];
int main()
{
in >> a >> b;
string rez;
rez = a + '#' + b;
int n = rez.size();
z[ 0 ] = n;
int leftt = 0;
int rightt = 0;
for (int i = 1; i < n; i++)
{
if (i > rightt)
{
leftt = rightt = i;
while (rez[rightt] == rez[rightt - leftt] && rightt < n)
{
rightt++;
}
z[leftt] = rightt - leftt;
rightt--;
} else
{
if (z[i - leftt] < rightt - i + 1)
{
z[i] = z[i - leftt];
} else
{
leftt = i;
while (rez[rightt] == rez[rightt - leftt] && rightt < n)
{
rightt++;
}
z[leftt] = rightt - leftt;
rightt--;
}
}
}
long long nr = 0;
for (int i = a.size() + 1; i < n; i++)
{
if (z[i] == a.size())
{
nr++;
}
}
out << nr << "\n";
for (int i = a.size() + 1; i < n; i++)
{
if (z[i] == a.size())
{
out << i - a.size() - 1 << " ";
}
}
return 0;
}