//时间复杂度O(N)
#include <stdio.h>
#include <cstring>
const int R = 26;
const int N = 250005; //字符串的长度
struct node{
node *next[R], *par;
int v; //该节点表示的子串的最大长度,最小长度即为par的最大长度+1,因此可以不用存下来
}nodes[N*2+100], *root;
int cnt; //树中节点个数
node* newNode(int v, node* par){
nodes[cnt].v = v;
nodes[cnt].par = par;
memset(nodes[cnt].next, 0, sizeof(node*)*R);
return &nodes[cnt++];
}
inline int id(char ch){
return ch-'a';
}
//构造后缀自动机
void SAM(char* str, node*& root){
cnt = 0;
node *last, *now, *np;
last = root = newNode(0, NULL);
int i, k;
for(i = 0; str[i]; i++){
now = last;
k = id(str[i]);
np = newNode(i+1, NULL);
while(now && ! now->next[k]){
now->next[k] = np;
now = now->par;
}
if(!now){
np->par = root;
}else if(now->next[k]->v == now->v+1){
np->par = now->next[k];
}else{
node* t = now->next[k];
node* nt = newNode(now->v+1, t->par);
t->par = np->par = nt;
memcpy(nt->next, t->next, sizeof(node*)*R);
while(now && now->next[k] == t){
now->next[k] = nt;
now = now->par;
}
}
last = np;
}
}
inline void upMax(int& a, int tmp){
if(a < tmp) a = tmp;
}
//求字符串sa和sb的最长公共连续子序列
int maxCommonLen(char* sa, char* sb){
cnt = 0;
SAM(sa, root);
//test();
node *now;
now=root;
int i, k, ans, len;
ans = len = 0;
for(i = 0; sb[i]; i++){
k = id(sb[i]);
if(now->next[k]){
len++;
now = now->next[k];
}else{
while(now && ! now->next[k]){
now = now->par;
}
if(now){
len = now->v + 1;
now = now->next[k];
}else{
now = root;
len = 0;
}
}
upMax(ans, len);
}
return ans;
}
分享到:
相关推荐
求两个字符串的最长公共子序列.pdf
最长公共子序列的算法实现,采用递归方法。
利用指针来查询两个字符串的最长公共子序列,并输出的算法。
给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence)。比如字符串1:BDCABA;字符串2:ABCBDAB。则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二、算法求解 这是一个...
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
自己编写的C++程序,求两个字符串的最长公共字串。例如a="abcrrrerads",b="afdabcssbcrrresswrds",则结果为bcrrre
本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= ,L1=s1.length,L2=s2....
查找两个字符序列的公共子序列,查找到的是两个字符串的所有公共子序列。
C++求最长公共子序列!实用 花费了好长时间!!
输入两个字符串, 求它们最长公共字串的长度
动态规划法求字符串最长公共子序列
算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS ...3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能
最长公共子序列问题就是给定两个序列X={x1,x2,...xm}和Y={y1,y2,...yn},找出X和Y的一个最长公共子序列。 Input 输入包含多组测试数据。第一行为一个整数C,表示有C组测试数据,接下来有C行数据,每组测试数据...
主要介绍了java实现求两个字符串最长公共子串的方法,是一道华为OJ上的一道题目,涉及Java针对字符串的遍历、转换及流程控制等技巧,需要的朋友可以参考下
采用动态规划法与回溯法实现了lcs算法,并显示各算法运行时间,便于对不同的输入数据测试这两个算法的优劣。
求解任意两个字符串的最长公共子序列