Pagini recente » Cod sursa (job #1144094) | Cod sursa (job #3235632) | Cod sursa (job #2950904) | Cod sursa (job #2523321) | Cod sursa (job #3287023)
//asta cica se cheama z
//vreau sa aflu de cate ori apare un prefix intr un vector v
//fie z[i] = lungimea maxima pt care [0, z[i] - 1] == [i, i + z[i] - 1]
//si [l, r] un interval cu R maxim pentru care [0, r - l] == [l, r] == z[l], pentru ca cu determinarea astora o sa te ocupi
//daca i pentru care vreau sa calculez z[i] > r, atunci fa brut si ia l = i
//cealata situatie este i apartine [l, r]
//atunci, fie k = i - l lungimea intervalului [l, i] - 1;
//avem ca z[i] >= min(z[k], r - i + 1), pentru ca minimul este lungimea pt care stim sigur ca v[k...] == v[i...]
//exista doua situatii acum
//z[k] < r - i + 1, deci diferenta apare in intervalul [0, r - l], pe care l am verificat
//caz in care e clar ca nu mai am nimic de facut decat sa avansez cu i
//si z[k] >= r - i + 1, in care nu mai stiu nimic despre unde apare diferenta
//asa ca faci brut
//numai ca de data asta iei l = i, ca sa foloseti faptul ca stii ca v[k, r - l] == v[i, r]
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int NMAX = 2e6;
int z[2 * NMAX + 2];
int main() {
int n, m;
string a, b, v;
cin >> a >> b;
v = a + '$' + b;
n = v.size();
m = a.size();
int l = 0, r = 0; //nu le initalizezi cu 1, n pt ca ideea e ca l, r se calculeaza pe masura ce mergi cu i
z[1] = n;
for (int i = 2; i <= n; i++) {
if (i > r) {
l = r = i;
while (r < n && v[r - l] == v[r])
r++;
z[i] = r - l;
r--;
}
else {
int k = i - l;
if (z[k] < r - i + 1)
z[i] = z[k];
else {
l = i;
while (r < n && v[r - l] == v[r])
r++;
z[i] = r - l;
r--;
}
}
}
vector<int> occurences;
for (int i = 0; i < n; i++)
if (z[i] == m)
occurences.push_back(i - m - 1);
cout << occurences.size() << '\n';
for (auto o : occurences)
cout << o << ' ';
}