hdu 6208 上一个kmp模板
2024-08-24 09:31:19
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
using namespace std;
int Next[];
string s[];
void getNext(string s)
{
int i,j;
i=;
j=-;
int len=s.length();
Next[]=-;
while(i<len && j<len)
{
if(j==- || s[i]==s[j]) Next[++i]=++j;
else j=Next[j];
}
}
bool kmp(string m,string s)
{
getNext(s);
int i,j;
i=j=;
int mlen=m.length();// i
int slen=s.length();// j
while(i<mlen && j<slen)
{
if(j==- || m[i]==s[j]) i++,j++;
else j=Next[j];
}
if(j==slen) return false;
return true;
}
int main()
{
cin.sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
string ms;
int mlen;
int flag=;
for(int i=;i<=n;i++)
{
cin>>s[i];
if(i==)
{
mlen=s[i].length();
ms=s[i];
}
else
{
int len=s[i].length();
if(len > mlen)
{
mlen=len;
ms=s[i];
}
}
}
flag=;
for(int i=;i<=n;i++)
{
//string now=q.front();
//q.pop();
string now=s[i];
int len=now.length();
if(len==mlen && now != ms)
{
flag=;
break;
}
//mq.push(now);
}
if(flag==) cout<<"No"<<endl;
else
{
int zflag=;
for(int i=;i<=n;i++)
{
string now=s[i];
if(kmp(ms,now))
{
zflag=;
break;
}
}
if(zflag==) cout<<"No"<<endl;
else cout<<ms<<endl;
}
}
return ;
}
// 补一发 kmp记录字串个数的
最新文章
- 学习 opencv---(5) 创建Trackbar(活动条) &;图像对比度,亮度值调整
- 用pygame学习初级python(二) 15.5.11
- Linux/Unix双机建立信任教程
- iOS出现<;object returned empty description>;的解决方法
- utime函数
- web压测工具http_load原理分析
- Android如何分析和研究Monkey Log文件
- Html方式导出word 页头和页脚设置
- MongoDB - The mongo Shell, mongo Shell Quick Reference
- 把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
- 1724: [Usaco2006 Nov]Fence Repair 切割木板( 贪心 )
- Python验证码识别处理实例(转)
- debian(wheezy) chrome beta 38.0.2x.xxx Shockwave Flash was crashed 该解决方案崩溃.
- WindowManager.LayoutParams的探究
- 自己动手写http服务器——主程序(三)
- 瞎j8封装第二版之数据层的封装
- MYSQL导入大量数据碰到的问题及解决方法
- git clone pytorch或caffe2速度慢的解决办法
- canvas API ,通俗的canvas基础知识(一)
- 使用CP进行应用层程序控制