Và tất nhiên để cài được full bài này bạn phải cài được thuật `O(n^2)` đã, nhưng mà chắc dễ thôi các bạn tự cài, mình lười viết (đang xem anime). Rồi các bạn sẽ dễ nhìn ra thôi là ta cần thay thế phần so sánh chuỗi bằng so sánh hash string.
Tham khảo code của
Sơn Đẹp Zai
Setup Sơn's define
// _____ _ _ // / ____| | | (_) // | (___ ___ _ __ __| | ___ _ __ ______ _ _ // \___ \ / _ \| '_ \ / _` |/ _ \ '_ \ |_ / _` | | // ____) | (_) | | | | | (_| | __/ |_) | / / (_| | | // |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_| // | | // |_|#include <bits/stdc++.h> #define nmax 100005 #define oo 10000000007 #define mod 1000000007 #define reset(x) memset(x, 0, sizeof x) #define PB(x) push_back(x) #define F first #define S second #define sonin cin #define sonout cout #define debug(x) cout << "Loli -> " << #x << " : " << x << "\n" #define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n" #define filename "TOWERBOX" #define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); #define fileN freopen(filename".inp", "r", stdin); #define fileX freopen(filename".out", "w", stdout); #define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZ(a) (int) a.size() #define FOU(x,a,b) for (lli x=a;x<=b;x++) #define FOD(x,a,b) for (lli x=a;x>=b;x--) #define FOA(a,b) for(auto &a:b) #define ALLvec(a) a.begin(),a.end() #define REU(x,a,b) for (lli x=a;x<b;x++) #define RED(x,a,b) for (lli x=a;x>b;x--) #define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i]; #define dembit1(x) __builtin_popcount(x) #define bit(x,i) ((x>>(i-1))&1ll) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1ll<<(i-1))) #define EL cout << "\n"; #define EX exit(0); #define Ary(x, i, j, a) x[(i - 1) * a + j] #define epsinon 1e-8 #define Son_onii_chan main #define times double stime = clock(); #define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n"; using namespace std; typedef long long lli; typedef long double ldo; typedef double dou; typedef vector vi; typedef vector vvi; typedef pair<lli, lli> pii; typedef vector vpi; typedef deque dqll;
O(k*n)
lli n, k; string T, P; lli base = 31; lli POW[nmax], hashT[nmax], hashP[nmax];lli getHashT(lli i, lli j) { return (hashT[j] - hashT[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD; } lli getHashP(lli i, lli j) { return (hashP[j] - hashP[i - 1] * POW[j - i + 1] + MOD * MOD) % MOD; }
int Son_onii_chan(){ //fileNX toiuuhoa sonin >> n >> k; sonin >> T; T = " " + T; POW[0] = 1; FOU(i,1,n) POW[i] = (POW[i - 1] * base) % MOD; hashP[0] = 0; hashT[0] = 0; FOU(i,1,n) hashT[i] = (hashT[i - 1] * base + T[i] - 'a' + 1) % MOD; while(k--){ sonin >> P; P = " " + P; if(P == T){ sonout << "YES\n"; continue; } FOU(i,1,n) hashP[i] = (hashP[i - 1] * base + P[i] - 'a' + 1) % MOD; bool ooi = false; FOU(i, 1, n-1) if(getHashP(1, i) == getHashT(n - i + 1, n) && getHashP(i+1, n) == getHashT(1, n-i)){ sonout << "YES\n"; ooi = true; break; } if(ooi) continue; sonout << "NO\n"; } return 0; }