Pagini recente » Cod sursa (job #2031430) | Cod sursa (job #612029) | Cod sursa (job #1709753) | Cod sursa (job #812738) | Cod sursa (job #2416924)
#include <bits/stdc++.h>
#define Nmax 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int N, M;
string A, B;
int Prefix[Nmax + 5];
int Answer[Nmax + 5];
int ans = 0;
static inline void generateMyPrefixes ();
int main()
{
fin >> A >> B;
generateMyPrefixes ();
int index = -1;
for (int i = 0; i < M; ++i)
{
while (0 <= index && A[index + 1] != B[i])
index = Prefix[index];
if (A[index + 1] == B[i])
++index;
if (index == N - 1)
Answer[++ans] = i - N + 1;
}
fout << ans << "\n";
ans = min (ans, 1000);
for (int i = 1; i <= ans; ++i)
fout << Answer[i] << " ";
return 0;
}
static inline void generateMyPrefixes ()
{
N = A.size ();
M = B.size ();
Prefix[0] = -1;
int index = -1;
for (int i = 1; i < N; ++i)
{
while (0 <= index && A[i] != A[index + 1])
index = Prefix[index];
if (A[i] == A[index + 1])
++index;
Prefix[i] = index;
}
}