Pagini recente » Cod sursa (job #3232224) | Cod sursa (job #891393) | Cod sursa (job #2465213) | Cod sursa (job #1778352) | Cod sursa (job #2905995)
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) std::cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) std::cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)std::cerr<<x[_]<<' ';std::cerr<<'\n',aaa
#define dbgs(x) std::cerr<<(#x)<<"[stl]: ";for(auto _:x)std::cerr<<_<<' ';std::cerr<<'\n',aaa
#define dbgp(x) std::cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define dbgsp(x) std::cerr<<(#x)<<"[stl pair]:\n";for(auto _:x)std::cerr<<_.fi<<' '<<_.se<<'\n';aaa
#define maxn 2000000
using namespace std;
string s, t;
int lps[maxn+5]; ///peste t.
int main () {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> t >> s;
int m = sz(t), n = sz(s);
s = " " + s;
t = " " + t;
lps[0] = lps[1] = 0;
int i, j, z;
///(t) construire cel mai lung prefix (diferit de tot sirul) care este si sufix.
for (i = 2; i <= m; i++) {
lps[i] = 0;
j = i;
while (j > 0) {
if (t[lps[j-1] + 1] == t[i]) {
lps[i] = lps[j-1] + 1;
break;
}
j = lps[j-1];
}
}
vi sol;
///pp ca am T[s..s+x-1] = P[0..x-1], nu mai merge inca un ch, adica T[s..s+x] = P[0..x].
///vreau s' minim, s+x > s' > s ai T[s'..s'+k-1] = P[0..k-1] SI s+x = s'+k.
///s' > s <=> k < x. vreau s' minim adica profit cat mai mult de bucata busita s..s+x-1, deci k maxim.
///T[s..s+x-1] = P[0..x-1], T[s'..s'+k-1] = P[0..k-1], s' > s => T[s..s+k-1] = P[0..k-1].
///deci T[s..s+k-1] = T[s'..s'+k-1]. adica k = lps[x].
i = 1;
j = 1;
while (i <= n-m+1) {
if (s[i+j-1] == t[j]) {
j++;
if (j > m) {
sol.pb(i);
i = i+m - lps[m];
j = lps[m] + 1;
}
} else {
if (j == 1) {
i++;
} else {
i = i+j-1 - lps[j-1];
j = lps[j-1] + 1;
}
}
}
fout << sz(sol) << '\n';
sol.resize(min(sz(sol), 1000));
for (int x: sol) fout << x-1 << ' ';
fin.close();
fout.close();
return 0;
}