Pagini recente » Cod sursa (job #674162) | Cod sursa (job #2537530) | Cod sursa (job #2089935) | Cod sursa (job #2043910) | Cod sursa (job #2977699)
// Atenție la indexarea elementelor de la poz 1 !!!
#include <bits/stdc++.h>
using namespace std;
string np = "strmatch";
ifstream f(np + ".in");
ofstream g(np + ".out");
// #define f cin
// #define g cout
int n, m, len, pi[2000003];
char v1[2000003], v2[2000003];
vector<int> rez(1024);
void citire(char v[], int &n)
{
string aux;
f >> aux;
n = aux.size();
for (int i = 0; i < aux.size(); i++)
v[i + 1] = aux[i];
}
void make_prefix()
{
for (int i = 2, q = 0; i <= n; i++)
{
while (q and v1[q + 1] != v1[i])
q = pi[q];
if (v1[q + 1] == v1[i])
q++;
pi[i] = q;
}
}
void kmp()
{
for (int i = 1, q = 0; i <= m; i++)
{
while (q and v1[q + 1] != v2[i])
q = pi[q];
if (v1[q + 1] == v2[i])
q++;
if (q == n)
{
len++;
if (len <= 1000)
rez[len] = i - n;
}
}
}
int main()
{
citire(v1, n);
citire(v2, m);
make_prefix();
kmp();
g << len << '\n';
for (int i = 1; i <= min(len, 1000); i++)
g << rez[i] << " ";
return 0;
}