Pagini recente » Cod sursa (job #506203) | Borderou de evaluare (job #716040) | Borderou de evaluare (job #1072218) | Borderou de evaluare (job #2272664) | Cod sursa (job #2985185)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a, b;
int pi[4000005];
void prefix_function()
{
int n = b.size();
pi[0] = 0;
for(int i = 1; i < n; i++)
{
int j = pi[i - 1];
while(j != 0 && b[j] != b[i])
j = pi[j - 1];
if(b[j] == b[i])
j++;
pi[i] = j;
}
}
signed main()
{
in >> a >> b;
b = a + "#" + b;
prefix_function();
int cnt = 0;
for(int i = a.size(); i < b.size(); i++)
{
if(pi[i] == a.size())
cnt++;
}
out << cnt << '\n';
int ok = 0;
for(int i = a.size(); i < b.size() && ok < 1000; i++)
{
if(pi[i] == a.size())
{
ok++;
int pos = i - (int)a.size() - (int)a.size();
out << pos << ' ';
}
}
return 0;
}