Pagini recente » Cod sursa (job #269689) | Cod sursa (job #2653775) | Cod sursa (job #1705477) | Cod sursa (job #2345117) | Cod sursa (job #2977687)
// 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, pi[2000003];
char v1[2000003], v2[2000003];
vector<int> rez;
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)
q = pi[n], rez.push_back(i - n);
}
}
int main()
{
citire(v1, n);
citire(v2, m);
make_prefix();
kmp();
g << rez.size() << '\n';
for (auto x : rez)
g << x << " ";
return 0;
}