Pagini recente » Cod sursa (job #205939) | Cod sursa (job #2010814) | Istoria paginii utilizator/popescovicescov | Cod sursa (job #251146) | Cod sursa (job #1498982)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout ("strmatch.out");
int n, m, V[2000010], S[1010];
char A[2000010], B[2000010];
void Read()
{
fin.get(A, 2000005, '\n');
n = strlen(A);
fin.get();
fin.get(B, 2000005, '\n');
m = strlen(B);
fin.close();
}
void Prefix()
{
for (int i = 1, k = 0; i < n; i++)
{
if (k && A[i] != A[k]) k = V[k - 1];
if (A[i] == A[k]) k++;
V[i] = k;
}
}
void Solve()
{
Prefix();
for (int i = 0, k = 0; i < m; i++)
{
while (k && B[i] != A[k]) k = V[k - 1];
if (B[i] == A[k]) k++;
if (k == n)
{
k = V[k - 1];
S[0] ++;
if (S[0] <= 1000) S[S[0]] = i - n + 1;
}
}
}
void Write()
{
fout << S[0] << '\n';
S[0] = min(S[0], 1000);
for (int i = 1; i <= S[0]; i++) fout << S[i] << ' ';
fout << '\n';
fout.close();
}
int main()
{
Read();
Solve();
Write();
return 0;
}