Blue Jeans POJ - 3080
题意：
给你n个DNA序列。（不超过10个）。 求： 公有的最长序列，假如有多个长度相等时。输出字典序最小的。
思路：
暴力枚举即可。
反思：
strcmp(const char *s1 , cosnt char *s2). s1>s2时，strcmp>0; s1<s2时，strcmp<0; s1=s2时，strcmp=0；strcpy(char *s, const char *p). 把p复制到s。strncpy(char *s, const char *p， const int len) 把p指针开始，到len长度复制到s。 （注意!!!!!!，要手动结尾，’\0’）string中的substr（位置，长度）。
AC（cstring）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std
;
const int maxn
=60+10;
char s
[11][maxn
];
int nxt
[maxn
], len
[maxn
];
char ans
[maxn
*maxn
][maxn
];
int num
=0;
void getnxt(char *p
){
int m
= strlen(p
);
int i
=0, j
=-1;
nxt
[0]=-1;
while(i
<m
){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
bool kmp(char *p
, char *s
){
int n
=strlen(s
),m
=strlen(p
);
int i
=0,j
=0;
while(i
<n
){
if(j
==-1||s
[i
]==p
[j
])i
++,j
++;
else j
=nxt
[j
];
if(j
==m
)return true;
}
return false;
}
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
int tt
;cin
>>tt
;
while(tt
--){
num
=0;
int n
;
cin
>>n
;
for(int i
=1; i
<=n
; i
++)cin
>>s
[i
];
bool f1
=false;
for(int i
=1; i
<=n
; i
++)len
[i
]=strlen(s
[i
]);
for(int k
= len
[1]; k
>=3 && !f1
; k
--){
for(int pos
=0; pos
<=len
[1]-k
; pos
++){
char p
[70];
strncpy(p
,s
[1]+pos
,k
);
p
[k
]='\0';
getnxt(p
);
int i
;
for(i
=2; i
<=n
&&kmp(p
,s
[i
]); i
++);
if(i
==n
+1){
f1
=true;
strcpy(ans
[num
++],p
);
}
}
}
char p
[70];
strcpy(p
,ans
[0]);
for(int i
=1; i
<num
; i
++)if(strcmp(ans
[i
],p
)<0)strcpy(p
,ans
[i
]);
if(f1
)cout
<<p
<<endl
;
else cout
<<"no significant commonalities"<<endl
;
}
return 0;
}
AC（string）
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std
;
int nxt
[70];
void getnxt(string p
){
int i
=0,j
=-1;
nxt
[0]=-1;
while(i
<p
.size()){
if(j
==-1||p
[i
]==p
[j
])nxt
[++i
]=++j
;
else j
=nxt
[j
];
}
}
bool kmp(string s
, string p
){
int i
=0,j
=0;
while(i
<s
.size()){
if(j
==-1||s
[i
]==p
[j
])i
++,j
++;
else j
=nxt
[j
];
if(j
==p
.size())return true;
}
return false;
}
string s
[12];
vector
<string
>ans
;
int main()
{
ios
::sync_with_stdio(0);cin
.tie(0);cout
.tie(0);
int tt
;cin
>>tt
;
while(tt
--){
ans
.clear();
int n
;cin
>>n
;
bool fl
=false;
for(int i
=1; i
<=n
; i
++)cin
>>s
[i
];
for(int k
=s
[1].size(); k
>=3&&!fl
; k
--){
for(int pos
=0; pos
<=s
[1].size()-k
; pos
++){
string p
=s
[1].substr(pos
,k
);
getnxt(p
);
int i
;
for(i
=2; i
<=n
&&kmp(s
[i
],p
); i
++);
if(i
==n
+1){
fl
=true;
ans
.push_back(p
);
}
}
}
if(fl
){
sort(ans
.begin(),ans
.end());
cout
<<ans
[0]<<endl
;
}else cout
<<"no significant commonalities"<<endl
;
}
return 0;
}
