Pagini recente » Cod sursa (job #1860749) | Cod sursa (job #1458170) | Cod sursa (job #1966831) | Cod sursa (job #2149597) | Cod sursa (job #2203997)
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int NMAX = 2e6 + 10;
string a, b;
vector <int> v;
int z[NMAX], len;
void Read()
{
ifstream fin("strmatch.in");
fin >> a >> b;
len = a.length();
fin.close();
}
void Solve()
{
a = a + "$" + b;
int left = 0, right = 0;
for (int k = 1;k < a.length();++k)
{
if (k > right)
{
left = right = k;
while (right < a.length() && a[right] == a[right - left])
++right;
z[k] = right - left;
--right;
}
else
{
int p = k - left;
if (z[p] < right - k + 1)
z[k] = z[p];
else
{
left = k;
while (right < a.length() && a[right] == a[right - left])
++right;
z[k] = right - left;
--right;
}
}
}
}
void Write()
{
ofstream fout("strmatch.out");
int cnt = 0, k = 0;
for (int i = len;i < a.length();++i)
{
if (z[i] == len)
{
++cnt;
if (cnt <= 1000)
v.push_back(i - len -1);
}
}
fout << cnt << "\n";
for (int i : v)
fout << i << " ";
fout.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}