Pagini recente » Cod sursa (job #1692468) | Cod sursa (job #298734) | Cod sursa (job #1593245) | Cod sursa (job #1556150) | Cod sursa (job #2800804)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b, s;
long long pi[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 + 2;
if(a_len > b_len)
{
fout << 0;
return 0;
}
k = 0;
for(int i = 2; i < s_len; i++)
{
while(k != 0 && s[i] != s[k + 1])
k = pi[k];
if(s[i] == s[k + 1])
k++;
pi[i] = k;
if(pi[i] == a_len)
{
afis++;
if(afis <= 1000)
ans[afis] = i - 1 - 2 * a_len;
}
}
fout << afis << '\n';
afis = min(afis, 1LL*1000);
for(int i = 1; i <= afis; i++)
fout << ans[i] << ' ';
return 0;
}