Pagini recente » Cod sursa (job #2217604) | Cod sursa (job #2978475) | Cod sursa (job #2353917) | Cod sursa (job #906600) | Cod sursa (job #2800816)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b, s;
long long z[4000005], k, afis, ans[1005], a_len, b_len, s_len;
int main()
{
fin >> a >> b;
s = a + '$' + b;
a_len = a.size();
b_len = b.size();
s_len = a_len + b_len + 1;
if(a_len > b_len)
{
fout << 0;
return 0;
}
int st = 0, dr = 0, k;
for(int i = 1; i < s_len; i++)
{
if(i > dr)
{
st = i;
dr = i;
while(dr < s_len && s[dr - st] == s[dr])
dr++;
z[i] = dr - st;
dr--;
}
else
{
k = i - st;
if(z[k] < dr - i + 1)
z[i] = z[k];
else
{
st = i;
while(dr < s_len && s[dr - st] == s[dr])
dr++;
z[i] = dr - st;
dr--;
}
}
if(z[i] == a_len)
{
afis++;
if(afis <= 1000)
ans[afis] = i - 1 - a_len;
}
}
fout << afis << '\n';
afis = min(afis, 1LL*1000);
for(int i = 1; i <= afis; i++)
fout << ans[i] << ' ';
return 0;
}