Pagini recente » Cod sursa (job #619964) | Cod sursa (job #2732258) | Cod sursa (job #17673) | Cod sursa (job #1839071) | Cod sursa (job #1123700)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int key[2000005], na, nb, n;
char a[2000005], b[2000005];
vector<int> sol;
void debug_key()
{
for(int i = 1; i <= na; i++)
printf("%d ", key[i]);
printf("\n");
}
void make_key()
{
int k = 0;
for(int i = 2; i <= na; i++)
{
while(k && a[i]!=a[k+1])
k = key[k];
if(a[i] == a[k+1])
k++;
key[i] = k;
}
// debug_key();
}
void solve()
{
int k = 0;
for(int i = 1; i <= nb; i++)
{
while(k && b[i]!=a[k+1])
k = key[k];
if(b[i] == a[k+1])
k++;
if(k == na)
{
n++;
if(n < 1000)
sol.push_back(i-na);
}
}
}
void afis()
{
printf("%d\n", n);
for(int i = 0; i< sol.size(); i++)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s\n", a+1, b+1);
na = strlen(a+1);
nb = strlen(b+1);
if(na > nb)
printf("0\n");
else
{
make_key();
solve();
afis();
}
return 0;
}