Pagini recente » Cod sursa (job #2735779) | Cod sursa (job #1478321) | Cod sursa (job #2857503) | Cod sursa (job #1176773) | Cod sursa (job #2591058)
#include <bits/stdc++.h>
#define ps push_back
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
string N, M;
int v[2000001];
vector <int> sol;
void make_prefix (string N)
{
int n = N.size (); //pattern
int j = 0;
for (int i = 1; i < n; i++)
{
if (N[i] != N[j])
while (j > 0 && N[j] != N[i])
j = v[j - 1];
if (N[j] == N[i])
++j;
v[i] = j;
}
}
void match (string N, string M)
{
int m = M.size (); //text
int n = N.size (); //pattern
int i = 0;
for (int j = 0; j < m; j++)
{
if (N[i] != M[j])
while (i > 0 && M[j] != N[i])
i = v[i - 1];
if (N[i] == M[j])
i++;
if (i == n)
{
sol.ps (j - i + 1);
i = v[i - 1];
}
}
}
int main ()
{
fin >> N >> M;
make_prefix (N);
match (N, M);
fout << sol.size () << "\n";
int n = sol.size ();
for (int i = 0; i < min (n , 1000); i++)
fout << sol[i] << " ";
}