Pagini recente » Cod sursa (job #1353288) | Cod sursa (job #2522450) | Cod sursa (job #2449614) | Cod sursa (job #1362648) | Cod sursa (job #2473417)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b, c;
int z[5000000], r, l, k, p, n1, n2, n3;
vector <int> ans;
int main()
{
fin >> a;
fin >> b;
c = a+b;
n1 = a.size();
n2 = b.size();
n3 = c.size();
for(int i = 1; i < n3; i++)
{
if(r < i)
{
k = i;
p = 0;
while(c[k] == c[p]) r = k, k++, p++, z[i]++;
if(r >= i) l = i;
}
else
{
p = i-l;
if(z[p] < r-i+1)
z[i] = z[p];
else
{
z[i] = r-i+1;
k = r+1;
p = z[p];
l = i;
while(c[p] == c[k])r = k, k++, p++, z[i]++;
}
}
}
for(int i = n1; i < n3; i++)
if(z[i] >= n1) ans.push_back(i-n1);
fout << ans.size() << '\n';
int n = ans.size();
for(int i = 0; i < n && i < 1000; i++)
fout << ans[i] << " ";
return 0;
}