首页 > 代码库 > HDU 1195 Open the Lock

HDU 1195 Open the Lock

2024-07-03 13:34:30   229人阅读

   问题描述：给出模板串A和子串B，长度分别为lenA和lenB，要求在线性时间内，对于每个A[i]（0<=i<lenA)，求出A[i..lenA-1]与B的最长公共前缀长度，记为ex[i]（或者说，ex[i]为满足A[i..i+z-1]==B[0..z-1]的最大的z值）。扩展KMP可以用来解决很多字符串问题，如求一个字符串的最长回文子串和最长重复子串。
   算法讲解：设next[i]为满足B[i..i+z-1]==B[0..z-1]的最大的z值（也就是B的自身匹配）。设目前next[0..lenB-1]与ex[0..i-1]均已求出，要用它们来求ex[i]的值。设p为目前A串中匹配到的最远位置，k为让其匹配到最远位置的值（或者说，k是在0<=i0<i的所有i0值中，使i0+ex[i0]-1的值最大的一个，p为这个最大值，即k+ex[k]-1），显然，p之后的所有位都是未知的，也就是目前还无法知道A[p+1..lenA-1]中的任何一位和B的任何一位是否相等。根据ex的定义可得，A[k..p]==B[0..p-k]，因为i>k，所以又有A[i..p]==B[i-k..p-k]，设L=next[i-k]，则根据next的定义有B[0..L-1]==B[i-k..i-k+L-1]。考虑i-k+L-1与p-k的关系：
    （1）i-k+L-1<p-k，即i+L<=p。这时，由A[i..p]==B[i-k..p-k]可以得到A[i..i+L-1]==B[i-k..i-k+L-1]，又因为B[0..L-1]==B[i-k..i-k+L-1]所以A[i..i+L-1]==B[0..L-1]，这就说明ex[i]>=L。又由于next的定义可得，A[i+L]必然不等于B[L]（否则A[i..i+L]==B[0..L]，因为i+L<=p，所以A[i..i+L]==B[i-k..i-k+L]，这样B[0..L]==B[i-k..i-k+L]，故next[i-k]的值应为L+1或更大），这样，可以直接得到ex[i]=L！
    （2）i+k-L+1>=p-k，即i+L>p。这时，首先可以知道A[i..p]和B[0..p-i]是相等的（因为A[i..p]==B[i-k..p-k]，而i+k-L+1>=p-k，由B[0..L-1]==B[i-k..i-k+L-1]可得B[0..p-i]==B[i-k..p-k]，即A[i..p]==B[0..p-i]），然后，对于A[p+1]和B[p-i+1]是否相等，目前是不知道的（因为前面已经说过，p是目前A串中匹配到的最远位置，在p之后无法知道任何一位的匹配信息），因此，要从A[p+1]与B[p-i+1]开始往后继续匹配（设j为目前B的匹配位置的下标，一开始j=p-i+1，每次比较A[i+j]与B[j]是否相等，直到不相等或者越界为止，此时的j值就是ex[i]的值）。在这种情况下，p的值必然会得到延伸，因此更新k和p的值。边界：ex[0]的值需要预先求出，然后将初始的k设为0，p设为ex[0] -1。对于求next数组，也是“自身匹配”，类似KMP的方法处理即可。唯一的不同点也在边界上：可以直接知道next[0]=lenB，next[1]的值预先求出，然后初始k=1，p=ex[1]。

 需要严重注意的是：在上述的情况（2）中，本该从A[p+1]与B[p-i+1]开始匹配，但是，若p+1<i，也就是p-i+1<0（这种情况是有可能发生的，当ex[i-1]=0，且前面的ex值都没有延伸到i及以后的时候）的话，需要将A、B的下标都加1（因为此时p必然等于i-2，如果A、B的下标用两个变量x、y控制的话，x和y都要加1）！！！！！

   代码：

int next[maxn],extend[maxn]; //extend[i]表示原串以第i开始与模式串的前缀的最长匹配
void EKMP(char s[],char t[])//s[]为主串，t[]为模版串
{
    int i,j,p,l;
    int len=strlen(t);
    int len1=strlen(s);
    memset(next,0,sizeof(next));
    memset(extend,0,sizeof(extend));
    next[0]=len;
    j=0;
    while(1+j<len&&t[j]==t[1+j])j++;
    next[1]=j;
    int a=1;
    for(i=2; i<len; i++)
    {
        p=next[a]+a-1;
        l=next[i-a];
        if(i+l<p+1)next[i]=l;
        else
        {
            j=max(0,p-i+1);
            while(i+j<len&&t[i+j]==t[0+j])j++;
            next[i]=j;
            a=i;
        }
    }
    j=0;
    while(j<len1&&j<len&&s[j]==t[j])j++;
    extend[0]=j;
    a=0;
    for(i=1; i<len1; i++)
    {
        p=extend[a]+a-1;
        l=next[i-a];
        if(l+i<p+1)extend[i]=next[i-a];
        else
        {
            j=max(0,p-i+1);
            while(i+j<len1&&j<len&&s[i+j]==t[j])j++;
            extend[i]=j;
            a=i;
        }
    }
}
代码来源：点击打开链接

文字来源：点击打开链接

    这些理论性的东西，看到一半实在是看不下去啦，，抓狂抓狂，，，，还是通过做题目来理解理论分析吧。。。做到相应的题目在加到本博文中吧。


联系
我们