Pagini recente » Cod sursa (job #2923047) | Cod sursa (job #1281111) | Cod sursa (job #976119) | Cod sursa (job #301801) | Cod sursa (job #2590479)
#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;
int j = 0;
int n = N.size ();
for (i = 1; i < n;)
{
if (N[i] == N[j])
{
j++;
v[i] = j;
i++;
}
else
{
if (j != 0)
j = v[j - 1];
else
{
v[i] = 0;
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] << " ";
}