Pagini recente » Cod sursa (job #2603178) | Cod sursa (job #344065) | Cod sursa (job #684917) | Cod sursa (job #1613811) | Cod sursa (job #2436177)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int a, b, d, x, y, n, m, nr;
int pi[1000];
int pos[1000];
string N, M;
void Prefix()
{
int k = 0;
pi[1] = 0;
for (int i = 2; i <= n; i++)
{
while (k > 0 && N[k] != N[i-1])
{
k = pi[k];
}
if (N[k] == N[i-1])
{
k = k + 1;
}
pi[i] = k;
}
}
void Kmp()
{
int q = 0;
for (int i = 1; i <= m; i++)
{
if (q > 0 && (N[q] != M[i-1]) )
{
q = pi[q];
}
if (N[q] == M[i-1])
{
q = q + 1;
}
if (q == n)
{
q = pi[n];
nr++;
if (nr <= 1000)
{
pos[nr] = i - n;
}
}
}
}
int main()
{
f >> N >> M;
n = N.size();
m = M.size();
Prefix();
Kmp();
g << nr<<"\n";
if (nr > 1000)
nr = 1000;
for (int i = 1; i <= nr; i++)
g << pos[i] << " ";
}