【来源】:bzoj3916

【参考博客】

BZOJ3916: [Baltic2014]friends

【 哈希和哈希表】Three Friends

【Baltic2014】【BZOJ3916】friends


【题解】

首先hash整个串,然后分成三种情况,分别是前半段,中间,后半段,三段的字母试图去掉看能否拼起来。

如果可以,那么还需要考虑是否为唯一的。

唯一的意思是: 串S,如果有选择两个不同的串S也能构成这个原串。

代码还是参考别人写的。

 #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int N = 2e6+;
typedef unsigned long long ull ;
const ull base = ; ull Pow[N],Hash[N];
ull Lstr , Rstr , S;
char str[N],Ans[N];
int n,Mid,pos=-; // NOT POSSIBLE = Odd or Not found a S
// NOT UNIQUE = exist least two S
// Else = The answer S // 切割字符串返回hash值
ull Cut_str( int L ,int R ){
ull ans = Hash[R] - Hash[L-] * Pow[R-L+] ;
return ans ;
} bool check (int i){
//如果未被标记过,则标记 返回true
//如果标记过,同时这个字符串和暂存的串不一样则返回false
if( pos == - || S == Lstr ){
pos = i ;
S = Lstr ;
return true ;
}else{
return false ;
}
}
int main()
{
scanf("%d%s",&n,str+);
Mid = n >> ; //偶数情况下无法构成
if( n%== ) return puts("NOT POSSIBLE"),; Pow[] = ;
for(int i=;i<=n;i++){
Pow[i] = Pow[i-] * base ;
Hash[i] = Hash[i-] * base + (ull)(str[i]-'A'+);
//所有字符串只包含大写英文字母
} // delete one character in [1,Mid]
for(int i= ; i<=Mid ; i++ ){
Lstr = Cut_str(,i-) * Pow[Mid+-i] + Cut_str(i+,Mid+);
Rstr = Cut_str(Mid+,n);
if( Lstr == Rstr ) if( !check(i) ) return puts("NOT UNIQUE"),;
} // delete Mid + 1
Lstr = Hash[Mid] ;
Rstr = Hash[n] - Hash[Mid+] * Pow[Mid];
if( Lstr == Rstr ) if( !check(Mid+) ) return puts("NOT UNIQUE"),; // delete [Mid+2,n] for(int i=Mid+ ; i<=n; i++ ){
Lstr = Hash[Mid];
Rstr = Cut_str(Mid+,i-) * Pow[n-i] + Cut_str(i+,n);
if( Lstr == Rstr ) if( !check(i) ) return puts("NOT UNIQUE"),;
} if( pos == - ){
return puts("NOT POSSIBLE"),;
} int len = n/,cnt = ;
for(int i=; i<=n && len ; i++ ){
if( pos == i ) continue;
Ans[cnt++] = str[i] ;
len -- ;
}
Ans[cnt] = '\0';
printf("%s\n",Ans);
return ;
} /* 7
ABXCABC */

最新文章

  1. Mysql 建立索引
  2. BZOJ 1584 DP
  3. synchronized同步对象锁
  4. Android  PNG透明图片转JPG格式背景变黑
  5. 教您如何检查oracle死锁,决解死锁
  6. HuffmanTree &amp;&amp; HuffmanCode
  7. Android自己的自动化测试Monkeyrunner和用法示例
  8. 破解 Adobe 系列的最佳方法,手把手教
  9. C# 获取当前年份的周期,周期所在日期范围
  10. Unable to preventDefault inside passive event listener
  11. LDAP-HA安装与配置(Keepalived方式实现)
  12. K/3 Cloud Web API接口说明文
  13. shell 字符串判断
  14. Win10系列:UWP界面布局进阶8
  15. 廖雪峰Java1-3流程控制-4switch多重选择
  16. Svn启动窗口报错 Could not load file or assembly &#39;SharpSvn.dll&#39; or one of its
  17. body{font-size: 62.5%;} 解释
  18. Java之IO(六)FileInputStream和FileOutputStream
  19. Velocity学习3
  20. React——JSX

热门文章

  1. elasticsearch集群部署以及head插件安装
  2. airflow自动生成dag
  3. How to install WireShark on Linux
  4. windows服务器安装nodejs实现自动计划
  5. php屏蔽电话号码中间四位
  6. HearthBuddy Magnetic 磁力
  7. torch学习中的难点
  8. centos7 开启80端口
  9. easyUI之ComboBox(下拉列表框)
  10. Hibernate3核心API简介-Transaction接口