Pagini recente » Cod sursa (job #783315) | Cod sursa (job #192142) | Cod sursa (job #1473121) | Cod sursa (job #1743421) | Cod sursa (job #2365726)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char B[2000100], A[2000100];
int p[2000100], m, n;
void pref()
{
int q = 0;
p[1] = 0;
for(int i = 2; i <= m;i++)
{
while(q && B[q + 1] != B[i])
q = p[q];
if(B[q + 1] == B[i])
q++;
p[i] = q;
}
}
int q, k, pos[2000100];
int main()
{
in.getline(B + 1, 2000002);
in.getline(A + 1, 2000002);
m = strlen(B + 1);
n = strlen(A + 1);
pref();
/*for(int i = 1;i <= m;i++)
cout << p[i] << " ";*/
for(int i = 1;i <= n;i++)
{
while(q && B[q + 1] != A[i])
q = p[q];
if(B[q + 1] == A[i])q++;
if(q == m)
{
q = p[m];
pos[++k] = i - m;
}
}
out << k << '\n';
for(int i = 1;i <= min(k, 1000);i++)
out << pos[i] << " ";
return 0;
}