题意：
给你两串小写字符串a和b，问能否将a拆成三段重新组成b
做法：
枚举拆分位置，也就是C(2,4999)。然后judge时用滚动哈希判断字符串是否匹配。
PS：
WA了好多发，因为爆int（忘记1LL，取模没取好...）。滚动哈希不一定能A，但基本都能A。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int hahb = 0; int f[5050]; int hah[5050]; string a, b; int len; bool judge( int i, int j) { int hah1 = hah[i-1]; int hah2 = (hah[j-1] - 1LL * hah[i-1] * f[j-i] % mod + mod) % mod; int hah3 = (hah[len-1] - 1LL * hah[j-1] * f[len - j] % mod + mod) % mod; // abc if ( ((1LL * hah1 * f[len-i] % mod + 1LL * hah2 * f[len-j] % mod) % mod + hah3) % mod == hahb ) return true ; // acb if ( ((1LL * hah1 * f[len-i] % mod + 1LL * hah3 * f[j-i] % mod) % mod + hah2) % mod == hahb ) return true ; // bac if ( ((1LL * hah2 * f[i+len-j] % mod + 1LL * hah1 * f[len-j] % mod) % mod + hah3) % mod == hahb ) return true ; // bca if ( ((1LL * hah2 * f[i+len-j] % mod + 1LL * hah3 * f[i] % mod) % mod + hah1) % mod == hahb ) return true ; // cab if ( ((1LL * hah3 * f[j] % mod + 1LL * hah1 * f[j-i] % mod) % mod + hah2) % mod == hahb ) return true ; // cba if ( ((1LL * hah3 * f[j] % mod + 1LL * hah2 * f[i] % mod) % mod + hah1) % mod == hahb ) return true ; return false ; } int main() { f[0] = 1; for ( int i = 1; i < 5010; i++) f[i] = (1LL * f[i-1] * 26) % mod; //记录进位 cin >> a >> b; len = a.size(); for ( int i = 0; i < len; i++) hahb = (1LL * hahb * 26 + b[i] - '0' ) % mod; //计算b的哈希值 hah[0] = a[0] - '0' ; for ( int i = 1; i < len; i++) { hah[i] = (1LL * hah[i-1] * 26 + a[i] - '0' ) % mod; //计算a[0]到a[i]字串的哈希值 } for ( int i = 1; i < len; i++) { for ( int j = i+1; j < len; j++) { if ( judge(i, j) ) { puts ( "YES" ); for ( int k = 0; k < len; k++) { if (k == i || k == j) putchar ( '\n' ); printf ( "%c" , a[k]); } putchar ( '\n' ); return 0; } } } puts ( "NO" ); } |