Pagini recente » Cod sursa (job #2607052) | Cod sursa (job #985519) | Cod sursa (job #298483) | Cod sursa (job #560423) | Cod sursa (job #2590453)
#include <bits/stdc++.h>
using namespace std;
int v[2000000];
vector <int> sol;
int cnt;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
void strstr (string N, string M)
{
int i = 0;
int j = 1;
int n = N.size ();
while (j < n)
{
if (N[i] != N[j])
i = 0;
if (N[i] != N[j])
{
v[j] = 0;
j++;
}
else
{
v[j] = i + 1;
j++;
i++;
}
}
i = 0;
j = 0;
int m = M.size ();
while (i < m)
{
if (N[j] == M[i])
{
i++;
j++;
}
else
{
if (j != 0)
j = v[j - 1];
if (N[j] == M[i])
{
i++;
j++;
}
else
i++;
}
if (j == n)
sol.push_back (i - n), cnt++;
}
}
int main ()
{
string n, m;
fin >> n;
fin >> m;
strstr (n, m);
fout << cnt << "\n";
for (int i = 0; i < sol.size () && i <= 999; i++)
fout << sol[i] << " ";
}