题意：对于一个字符串\(s\),复制一遍之后得到\(e\)，在\(e\)的任何位置插入一个字符形成\(u\)。给定\(u\)，求字符串\(s\). 字符串哈希。 考虑尝试每一个字符，尝试一下去除这个字符之后剩下的字符串是否能成功分成两部分。 用字符串哈希自带的“拼凑”功能即可。
#pragma GCC optimize("2") #include <bits/stdc++.h> #define PI 3.14159265 #define PQ priority_queue #define lowbit(x) ((x) & (-x)) #define rep(i , x , y) for(int (i) = (x) ; (i) <= (y) ; ++i) #define per(i , x , y) for(int (i) = (x) ; (i) >= (y) ; --i) //#define lmy #ifdef lmy #define DEBUG printf("Passing [%s] in LINE %d...\n" , __FUNCTION__ , __LINE__) #endif typedef long long ll; typedef unsigned long long ull; using namespace std; inline void read(int &x) { int f = 1;x = 0;char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } inline void readll(ll &x) { ll f = 1;x = 0;char ch = getchar(); while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } inline void print(int x) { if (x < 0) putchar('-'), x = -x;if (x > 9) print(x / 10);putchar(x % 10 + 48); } inline void printll(ll x) { if (x < 0) putchar('-'), x = -x;if (x > 9) print(x / 10);putchar(x % 10 + 48); } const int MaxN = 2000000 + 5; const ull bse = 13331; char a[MaxN]; int n; ull Pw[MaxN] , Hsh[MaxN]; vector <int> p; void HshPre() { Pw[0] = 1; rep(i , 1 , n + 1) Pw[i] = Pw[i - 1] * bse; rep(i , 1 , n) { Hsh[i] = Hsh[i - 1] * bse + (ull)(a[i]); } } ull HshValue(int l , int r) { return Hsh[r] - Hsh[l - 1] * Pw[r - l + 1]; } ull Merge(int l , int r , int ql , int qr) { // BaoZheng l , r < ql , qr ull HshValue1 = HshValue(l , r) , HshValue2 = HshValue(ql , qr); return HshValue1 * Pw[qr - ql + 1] + HshValue2; } bool Chksame(int l , int r , int ql , int qr) { return HshValue(l , r) == HshValue(ql , qr); } set <ull> obtain; void solve() { cin >> n; scanf("%s" , (a + 1)); //n = strlen(a + 1); if(!(n % 2)) { puts("NOT POSSIBLE"); return ; } HshPre(); rep(i , 1 , n) { if(i == 1) { if(Chksame(2 , (n + 1) / 2 , (n + 1) / 2 + 1 , n) && !obtain . count(HshValue(2 , (n + 1) / 2))) { // DEBUG; p . push_back(i); obtain . insert(HshValue(2 , (n + 1) / 2)); } } else if(i == n) { if(Chksame(1 , n / 2 , n / 2 + 1 , n - 1) && !obtain . count(HshValue(1 , n / 2))) { //DEBUG; p . push_back(i); obtain . insert(HshValue(1 , n / 2)); } } else if(i == (n + 1) / 2) { if(Chksame(1 , n / 2 , n - (n / 2) + 1 , n) && !obtain . count(HshValue(1 , n / 2))) { p . push_back(i) , obtain . insert(HshValue(1 , n / 2)); } } else if(i > (n + 1) / 2) { int l = 1 , r = n / 2; int pl = r + 1 , pr = i - 1; int ppl = i + 1 , ppr = n; ull V = Merge(pl , pr , ppl , ppr); if(V == HshValue(l , r) && !obtain . count(HshValue(l , r))) { p . push_back(i); obtain . insert(HshValue(l , r)); } } else if(i < (n + 1) / 2) { int l = n - (n / 2) + 1 , r = n; int pl = 1 , pr = i - 1; int ppl = i + 1 , ppr = l - 1; ull V = Merge(pl , pr , ppl , ppr); //if(i == 3) cout << V << "DBG , " << HshValue(l , r) << " Done\n"; if(V == HshValue(l , r) && !obtain . count(HshValue(l , r))) { p . push_back(i); obtain . insert(HshValue(l , r)); } } } if(p . size() == 0) { puts("NOT POSSIBLE"); return ; } else if(p . size() == 1) { int _ = p[0]; if(_ == 1) { rep(i , (n + 1) / 2 + 1 , n) putchar(a[i]); return ; } else if(_ == n) { rep(i , 1 , n / 2) putchar(a[i]); return ; } else if(_ == (n + 1) / 2) { rep(i , 1 , n / 2) putchar(a[i]); return ; } else if(_ > (n + 1) / 2) { rep(i , 1 , n / 2) putchar(a[i]); return ; } else if(_ < (n + 1) / 2) { rep(i , (n + 1) / 2 + 1 , n) putchar(a[i]); return ; } return ; } else if(p . size() > 1) { puts("NOT UNIQUE"); return ; } } int main(){ #ifdef lmy int nol_cl = clock(); #endif solve(); // did you forget to undefine Lmy ? #ifdef lmy printf("\nTime: %dms\n", int((clock() - nol_cl) / (double)CLOCKS_PER_SEC * 1000)); #endif return 0; }转载于:https://www.cnblogs.com/LiM-817/p/10887151.html
相关资源：数据结构—成绩单生成器