Pagini recente » Cod sursa (job #2796504) | Cod sursa (job #524199) | Cod sursa (job #817090) | Cod sursa (job #1919792) | Cod sursa (job #2203644)
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000006
#define MMAX 200009
#define kInf (1 << 30)
#define kInfLL (1LL << 60)
#define kMod 666013
#define edge pair<int, int>
#define x first
#define y second
#define USE_FILES "MLC"
#ifdef USE_FILES
#define cin fin
#define cout fout
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#endif
// number of tests from "in"
int test_cnt = 1;
void clean_test();
// your global variables are here
int n, m;
string subsir, sir;
int ant[NMAX];
void prefix() {
int k = 0; ant[1] = 0;
for (int i = 2; i <= n; ++i) {
while(subsir[k + 1] != subsir[i] && k > 0) k = ant[k];
if (subsir[k + 1] == subsir[i]) {
++k;
}
ant[i] = k;
}
}
// your solution is here
void solve() {
cin >> subsir;
cin >> sir;
n = subsir.size();
m = sir.size();
sir = ' ' + sir;
subsir = ' ' + subsir;
prefix();
int k = 0;
// daca sunt mai mult de 1000 de aparitii nu le mai afisez
// restrictie infoarena
vector<int>sol;
int nr = 0;
for (int i = 1; i <= m; ++i) {
while (subsir[k + 1] != sir[i] && k > 0) k = ant[k];
if (subsir[k + 1] == sir[i]) ++k;
if (k == n) {
k = ant[k];
if (nr < 1000) {
++nr;
sol.push_back(i - n);
}
}
}
cout << nr << "\n";
for (int i = 0; i < sol.size(); ++i) {
cout << sol[i] << " ";
}
if (test_cnt > 0) {
clean_test();
}
}
void clean_test() {
// clean if needed
}
int main() {
// cin >> test_cnt;
while (test_cnt--) {
solve();
}
return 0;
}