Pagini recente » Cod sursa (job #2373284) | Cod sursa (job #1478151) | Cod sursa (job #27385) | Cod sursa (job #1910784) | Cod sursa (job #2053621)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000005], B[2000005];
int N, M;
int P[2000005];
int Sol[1005];
void Read()
{
f.getline(A + 1, 2000005);
f.getline(B + 1, 2000005);
N = strlen(A + 1);
M = strlen(B + 1);
}
void pref()
{
int k = 0;
for(int i = 2; i <= N; i++)
{
while(k > 0 && A[i] != A[k + 1])
k = P[k];
if(A[i] == A[k + 1])
++k;
P[i] = k;
}
}
void Solve()
{
int k = 0, cnt = 0;
for(int i = 1; i <= M; i++)
{
while(k > 0 && B[i] != A[k + 1])
{
k = P[k];
}
if(B[i] == A[k + 1])
k++;
if(k == N)
{
++cnt;
if(cnt <= 1000)
Sol[cnt] = i - N + 1;
}
}
g << cnt << "\n";
for(int i = 1; i <= min(cnt, 1000); i++)
g << Sol[i] - 1 << " ";
g << "\n";
}
int main()
{
Read();
pref();
Solve();
return 0;
}