3450

news/2025/2/13 20:53:41/
/*
KMP来做532ms
*/// include file
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <ctime>#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <strstream>#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <list>
#include <functional>using namespace std;// typedef
typedef long long LL;
typedef unsigned long long ULL;// 
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
#define FORi(a,b,c) for(int i=(a);i<(b);i+=c)
#define FORj(a,b,c) for(int j=(a);j<(b);j+=c)
#define FORk(a,b,c) for(int k=(a);k<(b);k+=c)
#define FORp(a,b,c) for(int p=(a);p<(b);p+=c)#define FF(i,a)    for(int i=0;i<(a);i+++)
#define FFD(i,a)   for(int i=(a)-1;i>=0;i--)
#define Z(a) (a<<1)
#define Y(a) (a>>1)const double eps = 1e-6;
const double INFf = 1e10;
const int INFi = 1000000000;
const double Pi = acos(-1.0);template<class T> inline T sqr(T a){return a*a;}
template<class T> inline T TMAX(T x,T y)
{if(x>y) return x;return y;
}
template<class T> inline T TMIN(T x,T y)
{if(x<y) return x;return y;
}
template<class T> inline void SWAP(T &x,T &y)
{T t = x;x = y;y = t;
}
template<class T> inline T MMAX(T x,T y,T z)
{return TMAX(TMAX(x,y),z);
}// code begin
#define MAXN 4001
#define MAXM 202char dc[MAXN][MAXM];
int Len[MAXN];
int N;
int mins;
int minst;char P[MAXM];
int Ps;
int Ts;
int next[MAXM];char ans[MAXM];void CalNext()
{next[0] = 0;next[1] = 0;int j;FORi(2,Ps+1,1){j = next[i-1];while(true){if(P[j]==P[i-1]){next[i] = j+1;break;}if(j==0){next[i] = 0;break;}j = next[j];}}
}bool KMP(int cur)
{Ts = Len[cur];int i=0;int j=0;while(true){if(j==Ts) break;if(P[i]==dc[cur][j]){i++;j++;if(i==Ps){return true;}}else if(i>0){i=next[i];}elsej++;}return false;
}bool Isok()
{FORi(0,N,1){if(i!=mins){if(!KMP(i)){return false;}}}return true;
}int main()
{read;write;while(scanf("%d",&N)!=-1){if(N==0) break;minst = MAXM;FORi(0,N,1){scanf("%s",dc[i]);Len[i] = strlen(dc[i]);if(Len[i]<minst){minst = Len[i];mins = i;}}//找到了最短的子串 mins;for(int i=0;i<MAXM;i++)ans[i] = 'z';ans[MAXM] = 0;bool f=false;for(int len=Len[mins];len>0;len--){Ps = len;for(int i=0;i+len<=Len[mins];i++){strncpy(P,dc[mins]+i,len);P[len] = 0;CalNext();//然后和其余的串比较if(Isok()){if(strcmp(P,ans)<0){strcpy(ans,P);f=true;}}}if(f) break;}if(f) printf("%s\n",ans);else printf("IDENTITY LOST\n");}return 0;
}

转载于:https://www.cnblogs.com/ac2012/archive/2011/03/25/1995380.html


http://www.ppmy.cn/news/201293.html

相关文章

BZOJ3450 Easy

原题链接&#xff1a;http://www.lydsy.com/JudgeOnline/problem.php?id3450 Easy Description 某一天WJMZBMR在打osu~~~但是他太弱逼了&#xff0c;有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做&#xff0c;成功了就是o&#xff0c;失败了就是x&…

tjut 3450

/*分析:每次寻找以a[i]结尾的子序列能有多少个,只需要寻找a[i]-d和a[i]d之之间数结尾的子序列 的全部个数,然后把a[i]直接放在那些数后面即可 找寻和更新都是用树状数组 */ #include <iostream> #include <cstdio> #include <cstdlib> #include …

POJ 3450题解

题目连接 POJ 3450 Corporate Identity 思路 先用后缀数组处理出height数组&#xff0c;然后我们二分最长公共子串的长度&#xff0c;然后再height中找大于这个长度并且不在一个字符串的个数&#xff0c;如果等于n则返回true否则返回false即可。 前期一直TLE不知道为何&…

hdu 3450

吐吐槽吧&#xff1a;本来思路完全对了&#xff0c;但是那个二分查找搞错了&#xff0c;我还以为一个就可以了&#xff0c;结果查找上界和下界分别要一个查找函数&#xff08;WA时就看了一下别人的代码&#xff0c;发现别人都是用两个查找函数的&#xff0c;模仿别人写的查找函…

poj3450

Corporate Identity http://poj.org/problem?id3450 Description Beside other services, ACM helps companies to clearly state their “corporate identity”, which includes company logo but also other signs, like trademarks. One of such companies is Internet Bu…

HDU 3450(树状数组)

题目链接:HDU 3450 题目大意: 求长度大于等于且相邻差值不超过d的子序列的个数. 分析: 没什么好说的水题,就是没给a的范围真的天坑. 以下是代码: #include <set> #include <map> #include <stack> #include <queue> #include <vector> #inclu…

HDU 3450 Counting Sequences(树状数组+离散化+二分+dp思想 详细解答)

题目链接&#xff1a;HDU 3450 题意&#xff1a;给出一段序列&#xff0c;让你找出一段子序列&#xff08;长度>2&#xff09;满足序列中每相邻的两个数之间的差 <d&#xff0c;求出这样的序列的个数。 思路&#xff1a;本题利用dp思想&#xff0c;dp[i] 表示 以 i 为结…

小米路由器R1C或R1CM小米R1C 原厂Bootloader和epproom

想把刷机后的小米路由器R1C刷回小米原厂,而又没备份的小伙伴可以使用下面的BootLoader和epprom&#xff08;也就是原厂分区里面的Factory分区&#xff09;都是我自己手动备份的。 分享给大家 链接&#xff1a;https://pan.baidu.com/s/1v6iUB5idgxUPqclk2KJLkA 提取码&#x…