Hướng dẫn giải của VO 13 Bài 4 - Xử lý xâu
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; const int base1 = 59, base2 = 241, N = 1000100; char a[N], b[N]; int lenA, lenB; long long p1[N], p2[N], hashA1[N], hashA2[N], hashB1[N], hashB2[N]; int equal(int l, int r, int ll, int rr) { if ((hashA1[r] - hashA1[l - 1]) * p1[ll] != (hashB1[rr] - hashB1[ll - 1]) * p1[l]) return 0; if ((hashA2[r] - hashA2[l - 1]) * p2[ll] != (hashB2[rr] - hashB2[ll - 1]) * p2[l]) return 0; return 1; } char comp(int l, int r, int ll, int rr) { int low = 1, high = min(r - l, rr - ll) + 1, match = 0; while (low <= high) { int mid = (low + high) / 2; if (equal(l, l + mid - 1, ll, ll + mid - 1)) match = mid, low = mid + 1; else high = mid - 1; } if (l + match > r && ll + match > rr) return '='; if (l + match > r) return '<'; if (ll + match > rr) return '>'; return a[l + match] < b[ll + match] ? '<' : '>'; } int main() { cin >> lenA >> lenB; scanf("%s%s", a + 1, b + 1); p1[0] = p2[0] = 1; for (int i = 1; i <= 1000000; i++) { p1[i] = p1[i - 1] * base1; p2[i] = p2[i - 1] * base2; } for (int i = 1; i <= lenA; i++) { hashA1[i] = hashA1[i - 1] + p1[i - 1] * (a[i] - 'a'); hashA2[i] = hashA2[i - 1] + p2[i - 1] * (a[i] - 'a'); } for (int i = 1; i <= lenB; i++) { hashB1[i] = hashB1[i - 1] + p1[i - 1] * (b[i] - 'a'); hashB2[i] = hashB2[i - 1] + p2[i - 1] * (b[i] - 'a'); } int q, l, r, ll, rr; cin >> q; while (q--) { scanf("%d%d%d%d", &l, &r, &ll, &rr); printf("%c",comp(l, r, ll, rr)); } }
Code mẫu của ladpro98
program VOSTR; uses math; const fi=''; maxn=trunc(1e6)+6; b1 = trunc(1e4)+1; b2 = trunc(1e4)+7; bb1 = b1*b1; bb2 = b2*b2; var a,b:ansistring; na,nb,qq,q,i,l,r,m,maxL,oa,x,y,j,ll,l1,l2:longint; ha1,hb1,hb2,ha2:longint; hashA1,hashB1,hashA2,hashB2,pow1,pow2:array[0..maxn] of longint; inp:text; begin assign(inp,fi);reset(inp); readln(inp,na,nb); readln(inp,a);readln(inp,b); pow1[0]:=1;pow2[0]:=1;oa:=ord('a'); for i:=1 to max(na,nb) do pow1[i]:=(pow1[i-1]*26) mod b1; for i:=1 to max(na,nb) do pow2[i]:=(pow2[i-1]*26) mod b2; for i:=1 to na do hashA1[i]:=(hashA1[i-1]*26+ord(a[i])-oa) mod b1; for i:=1 to na do hashA2[i]:=(hashA2[i-1]*26+ord(a[i])-oa) mod b2; for i:=1 to nb do hashB1[i]:=(hashB1[i-1]*26+ord(b[i])-oa) mod b1; for i:=1 to nb do hashB2[i]:=(hashB2[i-1]*26+ord(b[i])-oa) mod b2; readln(inp,q); for qq:=1 to q do begin readln(inp,i,j,x,y); l1:=j-i;l2:=y-x; maxL:=min(l1,l2); Ll:=0;l:=0;r:=maxL; while l<=r do begin m:=(l+r) shr 1; hA1:=(hashA1[i+m]-pow1[m+1]*hashA1[i-1]+bb1) mod b1; hB1:=(hashB1[x+m]-pow1[m+1]*hashB1[x-1]+bb1) mod b1; hA2:=(hashA2[i+m]-pow2[m+1]*hashA2[i-1]+bb2) mod b2; hB2:=(hashB2[x+m]-pow2[m+1]*hashB2[x-1]+bb2) mod b2; if (hA1 = hB1) and (hA2=hB2) then begin Ll:=m; l:=m+1; end else r:=m-1; end; if Ll = maxL then begin if l1=l2 then write('=') else if l1<l2 then write('<') else write('>'); end else begin if a[i+Ll+1]<b[x+Ll+1] then write('<') else write('>'); end; end; end.
Code mẫu của RR
// VOSTR Solution by RR // O(Q*log(N)) #include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #include <fstream> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); const int MN = 2000111; int la, lb; char a[MN], b[MN]; long long ha[MN], hb[MN], p[MN]; void init() { p[0] = 1; FOR(i,1,2000000) p[i] = p[i-1] * 31; FOR(i,1,la) { ha[i] = ha[i-1] + p[i-1] * (long long) (a[i] - 'a'); } FOR(i,1,lb) { hb[i] = hb[i-1] + p[i-1] * (long long) (b[i] - 'a'); } } bool equal(int l, int r, int u, int v) { long long va = ha[r] - ha[l-1]; long long vb = hb[v] - hb[u-1]; return va * p[u] == vb * p[l]; } char compare(int l, int r, int u, int v) { int len1 = r - l + 1; int len2 = v - u + 1; int len = min(len1, len2); int left = 0, right = len, res = 0; while (left <= right) { int mid = (left + right) >> 1; if (equal(l, l+mid-1, u, u+mid-1)) { res = mid; left = mid + 1; } else right = mid - 1; } if (res == len) { if (len1 < len2) return '<'; else if (len1 > len2) return '>'; else return '='; } else { char ca = a[l+res]; char cb = b[u+res]; if (ca < cb) return '<'; else if (ca > cb) return '>'; else return '='; } } int main() { scanf("%d%d\n", &la, &lb); scanf("%s\n", &a[1]); scanf("%s\n", &b[1]); init(); int q; scanf("%d", &q); while (q--) { int l,r,u,v; scanf("%d%d%d%d", &l, &r, &u, &v); putchar(compare(l, r, u, v)); } puts(""); return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> using namespace std; typedef long long ll; typedef double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) //#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) //#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = {0, +1, 0, -1}; const int dc[] = {+1, 0, -1, 0}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const ll mod = (ll)1e9 + 7; #define maxn 1000005 char s1[maxn], s2[maxn], res[maxn]; int n, m, q; ll f1[maxn], f2[maxn], mu[maxn]; ll F1[maxn], F2[maxn], Mu[maxn]; bool cal(int l1, int r1, int l2, int r2){ return f1[r1] - f1[l1 - 1] * mu[r1 - l1 + 1] == f2[r2] - f2[l2 - 1] * mu[r2 - l2 + 1]; // && (F1[r1] - F1[l1 - 1] * Mu[r1 - l1 + 1] - (F2[r2] - F2[l2 - 1] * Mu[r2 - l2 + 1])) % mod == 0; } int main() { // freopen("in.txt", "r", stdin); cin >> n >> m; scanf("%s %s", s1, s2); f1[0] = 0; f2[0] = 0; F1[0] = 0; F2[0] = 0; mu[0] = 1; Mu[0] = 1; Rep(i, maxn - 1) { mu[i + 1] = mu[i] * mod; Mu[i + 1] = Mu[i] * inf % mod; } Rep(i, n) { f1[i + 1] = f1[i] * mod + s1[i]; F1[i + 1] = (F1[i] * inf + s1[i]) % mod; } Rep(i, m) { f2[i + 1] = f2[i] * mod + s2[i]; F2[i + 1] = (F2[i] * inf + s2[i]) % mod; } cin >> q; int l1, r1, l2, r2, l, r, mid; Rep(i, q){ scanf("%d %d %d %d", &l1, &r1, &l2, &r2); l = 1; r = min(r1 - l1, r2 - l2) + 2; while(l < r){ mid = (l + r) >> 1; if(cal(l1, l1 + mid - 1, l2, l2 + mid - 1)){ l = mid + 1; } else r = mid; } if(l == min(r1 - l1, r2 - l2) + 2){ if(r1 - l1 == r2 - l2) res[i] = '='; else if(r1 - l1 < r2 - l2) res[i] = '<'; else res[i] = '>'; } else{ if(s1[l1 + l - 2] < s2[l2 + l - 2]) res[i] = '<'; else res[i] = '>'; } } res[q] = '\0'; printf("%s", res); }
Bình luận