lzh

KMP算法是一种高效的模式匹配算法，复杂度可以达到O(m+n)，而普通模式匹配算法的复杂度为O(m*n)。

普通模式匹配算法

　　从主串的第一个字符（或者给定的第pos个字符）开始和子串的第一个字符开始比较，若相等，则继续比较后面的字符。若不相等，则从主串本次开始比较的字符的下一个字符开始，与子串的第一个字符进行比较（即主串需要回退到本次比较开始字符的下一字符，模式串回退到首字符，主串与子串都需要回退）。
　　匹配成功的标志：比较到子串的’\0’
　　匹配失败的标志：比较到主串的’\0’，且此时子串的比较位不等于’\0’。
　　算法复杂度：O(m*n)

KMP算法

KMP算法的改进思路
　　在普通匹配算法中子串与模式串都需要回溯，但这些回溯不是必要的。因为当某一位发生失配时，可以根据已匹配的结果进行判断。该算法问题可以理解为，当模式串中的第k位与主串的第i位比较时发生不匹配时，需要将模式串向右滑动到哪里继续与主串的第i位进行比较？避免了不必要的主串回溯，减少了模式串回溯的位数，从而使算法复杂度提升到O(m+n)。

KMP算法的实现思路
　　从主串的第一个字符（或者给定的第pos个字符）开始和子串的第一个字符开始比较，若相等，则继续比较后面的字符。若不相等，则将模式串右移至合适的位置，找出模式串中合适的第k位与主串中发生不等的位进行对齐比较。算法继续。
　　模式串与主串对齐继续比较的第k位必须满足其前k-1位与主串发生失配位置的前k-1位匹配，且该k-1位字串必须是最长的字串（即不存在k’>k，使模式串中的前k’-1位与主串发生失配位置的前k’-1位匹配，这是为了保证不漏过可以匹配的串）。
　　该算法中的主程序同普通的匹配算法类似，区别在于当发生不匹配时，主串指针不需要回退（不动），将模式串右移到合适的位置继续进行比较。当模式串移动到第一位（下标为0）仍然不等时，主串指针右移一位。该算法的关键是模式串next[]的取得。
　　匹配成功的标志：比较到子串的’\0’
　　匹配失败的标志：比较到主串的’\0’，且此时子串的比较位不等于’\0’。

next[]数组的获得
　　next[]数组记录了当模式串第j位发生失配时，模式串需要移动到第k位，使第k位与主串发生失配的位对齐继续比较（next[j]=k）。next[]数组使用递推实现，假设next[j]=k已经获得，则从next[j]开始推next[j+1]。具体算法如下。
　　假设next[j]=k（第j位及之前的next[]值已经求得，k<j），当模式串第j位发生失配时，模式串需要移动到第k位，使第k位与主串发生失配的位对齐继续比较。这说明：除了第k位，其前面的k-1位与主串发生失培的前k-1位已经匹配。（因为当第p[k]位失配时，p[1]p[2]…p[k-1]已经等于s[i-k+1]s[i-k+2]…s[i-1]）
　　而同时由于：p[j-k+1]p[j-k+2]…p[j-1]=s[i-k+1]s[i-k+2]…s[i-1]
　　所以：p[1]p[2]…p[k-1]= p[j-k+1]p[j-k+2]…p[j-1]

情况1：
　　若p[k]=p[j]，即p[next[j]]=p[j]，那么：p[1]p[2]…p[k-1]p[k]= p[j-k+1]p[j-k+2]…p[j-1]p[j]，则根据定义：next[j+1]=k+1=next[j]+1

情况2：
　　若p[k]!=p[j]，即p[1]p[2]…p[k-1]p[k]!= p[j-k+1]p[j-k+2]…p[j-1]p[j]，即p[k]与p[j]发生不等。把p[k]为模式串，即模式串第k位发生失配，根据KMP算法的基本思路，当模式串第k位发生失配时，模式串应移动到第next[k]=k’位与主串进行比较。此时：p[1]p[2]…p[k’-1]= p[j-k’+1]p[j-k’+2]…p[j-1]。然后再比较p[k’]与p[j]，若相等，同情况1：next[j+1]=k’+1= next[k]+1；若不相等，返回到情况2的头进行比较。（两种判断均可以归入情况1或者情况2，所以可以进行循环）

情况3：
　　若next[k]=-1，即发生失配元素的前一个元素与第一个元素a[0]仍然不等，该应使该失配元素直接与第一个元素比较，next[j+1]=0。（该情况可与第一种情况合并（因为next[0]=-1））

简单得说：
　　从next[j]=k开始比较，首先将k与自身对齐比较（找可以与j对齐比较的最长子串），如果相等，则p[k]=p[j]，满足情况1。若不相同，即模式串第k位发生失配，移动到k'=next[k]位继续进行比较。返回情况1或者2。如果next[k]=-1（仅第1位的next[0]的值为-1），说明j+1的前一位j与第一位比较仍然不等，那应该让第j+1位直接与第1位（下标为0）进行比较。
　　next[k+1]的计算依赖于next[k]，next[k+1]仅有一种方式获得，即第k+1字符的前面k个字符完全匹配（或者前一元素与第一个元素仍然不匹配）。而next[k]是已经计算的，即next[k]可以保证第k字符的前面k-1个字符（除了第k个字符）完全匹配，而且该字串是最长字串。因为只需比较第k个字符是否匹配。匹配成功即情况一，匹配失败则继续寻找next[next[k]]。
　　编程时，每次进行计算next[j+1]时，必须保证j与k呈对应关系，即每新一次计算前，next[j]=k（next[j+1]=k+1，因而也可以写成next[++j]=++k）。

KMP算法的再改进

　　当第k+1位发生失配时，根据原算法，可以找到一个子串，与之匹配。此时，next[j+1]=k+1
但若 T[j+1]= T[next[j+1]]=T[k+1]，则当T[j+1]发生失配时，程序会使回到第next[j+1](=k+1)位，与T[j+1]所对应的主串字符进行比较。但由于主串字符已经不等于T[j+1]，因而也必然不等于T[next[j+1]]，因而此次比较必然失败。
　　改进：当T[j+1]= T[next[j+1]]=T[k+1]时，next[j+1]= next[next[j+1]]=next[k+1]，从而避免不必要的重复比较。

附：
普通模式匹配算法代码：
int mystrstr(char* S, char* T, int pos)
{
    int i=pos; //设置主串的指针位置（初始位置为给定的开始位置）
    int j=0; //设置子串的指针位置（初始位置为子串的首元素）
    
    while (S[i]!='\0')
    {
          if (T[j]=='\0') {return (i-j+1);} //比较到子串的’\0’，匹配成功
          if (S[i]==T[j]) {
             i++;
             j++;
            //子串与主串在该位的匹配值相等，则继续比较下一字符
          } else { //若不相同
            i=i-j+1; //主串回退到本次比较开始字符的下一字符 
            j=0; //模式串回退到首字符
          }
    }
    return 0; 比较到主串的’\0’，且此时子串的比较位不等于’\0’，匹配失败
}

KMP主程序代码：
int mystrstr(char* S, char* T, int pos, const int* next)
{
    int i=pos; //主串指针 
    int j=0; //模式串指针 
    
    while (S[i]!='\0') //当主串指针所指字符不为'\0'时,继续比较 
    {     
          
          if (j==-1) {i++;j++;}
          // 当头元素仍然不匹配时,j=-1,此时j指针清0指向模式串的首元素, i指针指下主串的下一元素 
          if (T[j]=='\0') {return (i-j+1);}
          // 当模式串指针所指元素为'\0'时,匹配完成,返回位置 
          if (S[i]==T[j]) {
             i++;
             j++;
             //当模式串指针与主串指针所指元素相同时,两指针都相加.比较下一元素 
          } else {
            j=next[j];
            //若模式串指针与主串指针所指内容不同时,模式串指针回退指到next[j]位置(第j位发生失配) 
          }
    }
    return 0;
}

生成next[]数组代码
//该程序用next[i]来推测next[i+1]
//每次比较开始时next[i]=k,每次比较开始前i与k成对应关系 
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1; //k为当第j位发生失配时,需要移动到的下一次进行比较的位(第k位)            
     next[0]=-1;
     //给定初始值,当比较到第一个元素(下标为0)仍然不等时,k的值为-1 
     
     while (j<strlen(T)) //j的大小有strlen(T)个,下标从0开始 
     {
           if (k==-1||T[k]==T[j])
           {
              //next[j]=k的定义为: t[0]...t[k-1]=t[j-k+1]...t[j-1] 
              //当T[k]=T[j]时,即T[next[j]]=T[j]时,T[1]...T[k]=T[j-k+1]...T[j],此时next[j+1]=next[j]+1=k+1,即可以求出next[j+1] 
              //当k=1时,即j+1的前一个元素与模式串的首元素相比,仍然不同,则应该让第j+1个元素直接与首元素进行比较 
              next[j+1]=k+1;
              j++; 
              k++; //k=next[j+1]=k+1,不能写k=next[j+1],因为上面一句j已经变化过了
              //next[j+1]=next[j]+1=k+1,即j+1与k+1是成对出现的 
              //下次比较开始前,j与k必须成对应关系出现, 满足这个式子：next[j+1]=k+1
           } else {
               k=next[k];
               //如果不等,可以理解为模式串的第k(next[j])位发生不匹配
               //则寻找到第next[k]位(保证k之前的元素匹配)继续进行比较
               }
     }
}

生成KMP改进算法的next[]数组代码
void GetNext (char* T,int* next)
{
     int j=0;
     int k=-1;

     next[0]=-1;
     // next[j]=k
     
     while (j<strlen(T))
     {
           if (k==-1||T[k]==T[j])
           {
              next[j+1]=k+1;
              
              if (T[j+1]==T[next[j+1]]) {
                 next[j+1]=next[next[j+1]];
              } 
              //就多了这段，当T[j+1]与T[next[j+1]]相等时，使next[j+1]=next[next[j+1]]
              j++;
              k++;
           } else {
               k=next[k];
               }
     }                 
}


本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/ultrasurf/archive/2007/11/08/1873589.aspx

 1 /*并查集学习：
 2 
 3 并查集：(union-find sets)
 4 
 5 一种简单的用途广泛的集合. 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多，如其求无向图的连通分量个数等。最完美的应用当属：实现Kruskar算法求最小生成树。
 6 
 7 l         并查集的精髓（即它的三种操作，结合实现代码模板进行理解）：
 8 
 9 1、unit(x) 把每一个元素初始化为一个集合
10 
11 初始化后每一个元素的父亲节点是它本身，每一个元素的祖先节点也是它本身（也可以根据情况而变）。
12 
13 2、find(x) 查找一个元素所在的集合
14 
15 查找一个元素所在的集合，其精髓是找到这个元素所在集合的祖先！这个才是并查集判断和合并的最终依据。
16 判断两个元素是否属于同一集合，只要看他们所在集合的祖先是否相同即可。
17 合并两个集合，也是使一个集合的祖先成为另一个集合的祖先，具体见示意图
18 
19 3、connect(x,y) 合并x,y所在的两个集合
20 
21 合并两个不相交集合操作很简单：
22 利用find找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先。
23          并查集的优化
24 
25 1、find(x)时 路径压缩
26 寻找祖先时我们一般采用递归查找，但是当元素很多亦或是整棵树变为一条链时，每次find(x)都是O(n)的复杂度，有没有办法减小这个复杂度呢？
27 答案是肯定的，这就是路径压缩，即当我们经过"递推"找到祖先节点后，"回溯"的时候顺便将它的子孙节点都直接指向祖先，这样以后再次find(x)时复杂度就变成O(1)了，如下图所示；可见，路径压缩方便了以后的查找。
28 
29 
30 2、connect(x,y)时 按秩合并
31 即合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小。
32 */
33 
34 #include<iostream>
35 using namesfatherace std;
36 
37 int father[30001];//各个元素的父节点数组
38 int h[30001];//哥哥元素的高度
39 
40 void Init(int n)
41 {
42     for(int i=0;i<n;i++)
43     {
44         father[i]=i;
45         h[i]=0;
46     }
47 }
48 
49 int find(int x)
50 {
51     if(x!=father[x])
52         father[x]=find(father[x]);
53     return father[x];
54 }
55 
56 void connect(int a,int b)
57 {
58     int x,y;
59     x=find(a);
60     y=find(b);
61     if(x==y)
62         return ;
63     if(h[x]<h[y])
64         father[x]=y;
65     else
66     {
67         if(h[x]==h[y])
68             h[x]++;
69         father[y]=x;
70     }
71 }
72 
73 int main()
74 {
75     int k,a,i,m,n,num,t,first;
76     Init(20);
77     cin>>k;
78     while(k--)
79     {
80         cin>>m>>n;
81         
82         connect(m,n);
83     }
84     for(i=1;i<=10;i++)
85     {
86         cout<<i<<"的父节点为: "<<father[i]<<"  高度:"<<h[i]<<endl;
87     }
88     return 0;
89 }