Pagini recente » Cod sursa (job #3328089) | Borderou de evaluare (job #2660618) | Cod sursa (job #72295) | Borderou de evaluare (job #3120808) | Cod sursa (job #3340593)
/// patratele
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000003
#define NMAX 2000005
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int i, pi[NMAX], la, lb, pib[NMAX], ras[NMAX], vf;
char a[NMAX], b[NMAX];
void py()
{
la = strlen(a);
int k = 0;
for (i = 1; i < la; i++)
{
while (k != 0 && a[k] != a[i])
k = pi[k - 1];
if (a[k] == a[i])
k++;
pi[i] = k;
}
}
int main()
{
// ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
fin >> a >> b;
py();
lb = strlen(b);
int k = 0;
for (i = 0; i < lb; i++)
{
while (k!=0 && a[k] != b[i])
k = pi[k - 1];
if (a[k] == b[i])
k++;
//pib[i] = k;
if (pi[i] == la)
ras[++vf] = i - la + 1;
}
fout << vf << '\n';
for (i = 1; i <= min(1000, vf); i++)
fout << ras[i] << " ";
return 0;
}