POJ-3080-Blue jeans(KMP, 暴力)
2024-09-05 10:37:04
链接:
https://vjudge.net/problem/POJ-3080#author=alexandleo
题意:
给你一些字符串,让你找出最长的公共子串。
思路:
暴力枚举第一个串的子串,挨个匹配接下来的所有串.
找出最长子串中, 字典序最小的.
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
//#include <memory.h>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <stack>
#include <string>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <sstream>
#define MINF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e6+10;
int Next[MAXN];
string s[20];
int n;
void GetNext(string p)
{
int len = p.length();
Next[0] = -1;
int j = 0;
int k = -1;
while (j < len-1)
{
if (k == -1 || p[k] == p[j])
{
++k;
++j;
Next[j] = k;
}
else
k = Next[k];
}
}
bool Kmp(string ss, string p)
{
int lens = ss.length();
int lenp = p.length();
int i = 0, j = 0;
while (i < lens && j < lenp)
{
if (j == -1 || ss[i] == p[j])
{
i++;
j++;
}
else
j = Next[j];
}
return j == lenp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
string res = "";
cin >> n;
for (int i = 1;i <= n;i++)
cin >> s[i];
int len = s[1].length();
for (int i = 0;i < len;i++)
{
for (int j = i;j < len;j++)
{
string tmp(s[1], i, j-i+1);
GetNext(tmp);
bool flag = true;
for (int k = 2;k <= n;k++)
{
if (!Kmp(s[k], tmp))
{
flag = false;
break;
}
}
if (flag)
{
if (tmp.length() > res.length())
res = tmp;
if (tmp.length() == res.length() && tmp < res)
res = tmp;
}
}
}
if (res.length() >= 3)
cout << res << endl;
else
cout << "no significant commonalities" << endl;
}
return 0;
}
最新文章
- C#记录程序运行时间记录显示
- ACM集训的第一题
- erlang 查看内存消耗的方法?
- 查看 并发请求数及其TCP连接状态【转】
- 从零开始学ios开发(四):IOS控件(1),Image View、Text Field、Keyboard
- 通用多目录makefile的写法
- (原)ubuntu16中简单的使用google的protobuf
- HUST 1027 Enemy Target!
- python之基础中的基础(三)
- Java是如何解析xml文件的(DOM)
- github page博客里添加多说评论插件
- 【嵌入式开发】C语言 指针数组 多维数组
- Canadian-dollar_RMB
- Java坦克大战(四)
- python基础3--字符串
- yasm开源汇编器分析
- 马婕 2014MBA专硕考试 词汇每日一练(转)
- Shiro 修改权限,刷新权限
- SVM初学
- 转载 二十篇java技术热文