KMP 算法，能看懂的一个讲解
Richard Lu 发表于 2010-12-21 17:45:43
KMP字符串模式匹配详解
KMP字符串模式匹配详解
来自CSDN A_B_C_ABC 网友
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一． 简单匹配算法
先来看一个简单匹配算法的函数：
int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符
起存在和串 T 相同的子串，则称匹配成功，返回第一个
这样的子串在串 S 中的下标，否则返回 -1 */
int i = pos, j = 0;
while ( S[i+j] != '#CONTENT#'&& T[j] != '#CONTENT#')
if ( S[i+j] == T[j] )
j ++; // 继续比较后一字符
else
{
i ++; j = 0; // 重新开始新的一轮匹配
}
if ( T[j] == '#CONTENT#')
return i; // 匹配成功 返回下标
else
return -1; // 串S中(第pos个字符起)不存在和串T相同的子串
} // Index_BF
此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。
例如：在串S=”abcabcabdabba”中查找T=” abcabd”（我们可以假设从下标0开始）:先是比较S[0]和T[0]是否相等，然后比较S[1] 和T[1]是否相等…我们发现一直比较到S[5] 和T[5]才不等。如图：
当这样一个失配发生时，T下标必须回溯到开始，S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图：
这次立刻发生了失配，T下标又回溯到开始，S下标增1,然后再次比较。如图：
又一次发生了失配，所以T下标又回溯到开始，S下标增1,然后再次比较。这次T中的所有字符都和S中相应的字符匹配了。函数返回T在S中的起始下标3。如图：
二. KMP匹配算法
还是相同的例子，在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==’d’的模式函数值（next[5]=2，为什么？后面讲），直接比较S[5] 和T[2]是否相等，因为相等，S和T的下标同时增加;因为又相等，S和T的下标又同时增加。。。最终在S中找到了T。如图：
KMP匹配算法和简单匹配算法效率比较，一个极端的例子是：
在S=“AAAAAA…AAB“(100个A)中查找T=”AAAAAAAAAB”, 简单匹配算法每次都是比较到T的结尾，发现字符不同，然后T的下标回溯到开始，S的下标也要回溯相同长度后增1，继续比较。如果使用KMP匹配算法，就不必回溯.
对于一般文稿中串的匹配，简单匹配算法的时间复杂度可降为O (m+n)，因此在多数的实际应用场合下被应用。
KMP算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。看前面的例子。为什么T[5]==’d’的模式函数值等于2（next[5]=2），其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同，且T[5]==’d’不等于开始的两个字符之后的第三个字符（T[2]=’c’）.如图：
也就是说，如果开始的两个字符之后的第三个字符也为’d’,那么，尽管T[5]==’d’的前面有2个字符和开始的两个字符相同，T[5]==’d’的模式函数值也不为2，而是为0。
前面我说：在S=”abcabcabdabba”中查找T=”abcabd”，如果使用KMP匹配算法，当第一次搜索到S[5] 和T[5]不等后，S下标不是回溯到1，T下标也不是回溯到开始，而是根据T中T[5]==’d’的模式函数值，直接比较S[5] 和T[2]是否相等。。。为什么可以这样？
刚才我又说：“（next[5]=2），其实这个2表示T[5]==’d’的前面有2个字符和开始的两个字符相同”。请看图 ：因为，S[4] ==T[4]，S[3] ==T[3]， 根据next[5]=2，有T[3]==T[0]，T[4] ==T[1]，所以S[3]==T[0]，S[4] ==T[1]（两对相当于间接比较过了），因此，接下来比较S[5] 和T[2]是否相等。。。
有人可能会问：S[3]和T[0]，S[4] 和T[1]是根据next[5]=2间接比较相等，那S[1]和T[0]，S[2] 和T[0]之间又是怎么跳过，可以不比较呢？因为S[0]=T[0]，S[1]=T[1]，S[2]=T[2]，而T[0] != T[1], T[1] != T[2],==> S[0] != S[1],S[1] != S[2],所以S[1] != T[0],S[2] != T[0]. 还是从理论上间接比较了。
有人疑问又来了，你分析的是不是特殊轻况啊。
假设S不变，在S中搜索T=“abaabd”呢？答：这种情况，当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=-1，意思是S[2]已经和T[0] 间接比较过了，不相等，接下来去比较S[3]和T[0]吧。
假设S不变，在S中搜索T=“abbabd”呢？答：这种情况当比较到S[2]和T[2]时，发现不等，就去看next[2]的值，next[2]=0，意思是S[2]已经和T[2]比较过了，不相等，接下来去比较S[2]和T[0]吧。
假设S=”abaabcabdabba”在S中搜索T=“abaabd”呢？答：这种情况当比较到S[5]和T[5]时，发现不等，就去看next[5]的值，next[5]=2，意思是前面的比较过了，其中，S[5]的前面有两个字符和T的开始两个相等，接下来去比较S[5]和T[2]吧。
总之，有了串的next值，一切搞定。那么，怎么求串的模式函数值next[n]呢？（本文中next值、 模式函数值、 模式值 是一个意思。）
三. 怎么求串的模式值next[n]
定义：
（1）next[0]= -1 意义：任何串的第一个字符的模式值规定为-1。
（2）next[j]= -1 意义：模式串T中下标为j的字符，如果与首字符
相同，且j的前面的1—k个字符与开头的1—k
个字符不等（或者相等但T[k]==T[j]）（1≤k<j）。
如：T=”abCabCad” 则 next[6]=-1，因T[3]=T[6]
（3）next[j]=k 意义：模式串T中下标为j的字符，如果j的前面k个
字符与开头的k个字符相等，且T[j] != T[k] （1≤k<j）。
即T[0]T[1]T[2]。。。T[k-1]==
T[j-k]T[j-k+1]T[j-k+2]…T[j-1]
且T[j] != T[k].（1≤k<j）;
(4) next[j]=0 意义：除（1）（2）（3）的其他情况。
举例：
01）求T=“abcac”的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据 (4) 因（3）有1<=k<j;不能说，j=1,T[j-1]==T[0]
next[2]=0 根据 (4) 因（3）有1<=k<j;（T[0]=a）!=（T[1]=b）
next[3]= -1 根据 (2)
next[4]=1 根据 (3) T[0]=T[3] 且 T[1]=T[4]
即
下标 | 0 | 1 | 2 | 3 | 4 |
T | a | b | c | a | c |
next | -1 | 0 | 0 | -1 | 1 |
若T=“abcab”将是这样：
下标 | 0 | 1 | 2 | 3 | 4 |
T | a | b | c | a | b |
next | -1 | 0 | 0 | -1 | 0 |
为什么T[0]==T[3],还会有next[4]=0呢, 因为T[1]==T[4], 根据 (3)” 且T[j] != T[k]”被划入（4）。
02）来个复杂点的，求T=”ababcaabc” 的模式函数的值。
next[0]= -1 根据（1）
next[1]=0 根据 (4)
next[2]=-1 根据 (2)
next[3]=0 根据 (3) 虽T[0]=T[2] 但T[1]=T[3] 被划入（4）
next[4]=2 根据 (3) T[0]T[1]=T[2]T[3] 且T[2] !=T[4]
next[5]=-1 根据 (2)
next[6]=1 根据 (3) T[0]=T[5] 且T[1]!=T[6]
next[7]=0 根据 (3) 虽T[0]=T[6] 但T[1]=T[7] 被划入（4）
next[8]=2 根据 (3) T[0]T[1]=T[6]T[7] 且T[2] !=T[8]
即
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | a | b | a | b | c | a | a | b | c |
next | -1 | 0 | -1 | 0 | 2 | -1 | 1 | 0 | 2 |
只要理解了next[3]=0，而不是=1，next[6]=1，而不是= -1，next[8]=2，而不是= 0，其他的好象都容易理解。
03) 来个特殊的，求 T=”abCabCad” 的模式函数的值。
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
T | a | b | C | a | b | C | a | d |
next | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 4 |
next[5]= 0 根据 (3) 虽T[0]T[1]=T[3]T[4],但T[2]==T[5]
next[6]= -1 根据 (2) 虽前面有abC=abC,但T[3]==T[6]
next[7]=4 根据 (3) 前面有abCa=abCa,且 T[4]!=T[7]
若T[4]==T[7]，即T=” adCadCad”,那么将是这样：next[7]=0, 而不是= 4,因为T[4]==T[7].
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
T | a | d | C | a | d | C | a | d |
next | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 |
如果你觉得有点懂了，那么
练习：求T=”AAAAAAAAAAB” 的模式函数值，并用后面的求模式函数值函数验证。
意义：
next 函数值究竟是什么含义，前面说过一些，这里总结。
设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
1. next[n]= -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0]
2. next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。
3. next[n]= k >0 但k<n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？
4. 其他值，不可能。
四. 求串T的模式值next[n]的函数
说了这么多，是不是觉得求串T的模式值next[n]很复杂呢？要叫我写个函数出来，目前来说，我宁愿去登天。好在有现成的函数，当初发明KMP算法，写出这个函数的先辈，令我佩服得六体投地。我等后生小子，理解起来，都要反复琢磨。下面是这个函数:
void get_nextval(const char *T, int next[])
{
// 求模式串T的next函数值并存入数组 next。
int j = 0, k = -1;
next[0] = -1;
while ( T[j/*+1*/] != '#CONTENT#' )
{
if (k == -1 || T[j] == T[k])
{
++j; ++k;
if (T[j]!=T[k])
next[j] = k;
else
next[j] = next[k];
}// if
else
k = next[k];
}// while
////这里是我加的显示部分
// for(int i=0;i<j;i++)
//{
// cout<<next[i];
//}
//cout<<endl;
}// get_nextval
另一种写法，也差不多。
void getNext(const char* pattern,int next[])
{
next[0]= -1;
int k=-1,j=0;
while(pattern[j] != '#CONTENT#')
{
if(k!= -1 && pattern[k]!= pattern[j] )
k=next[k];
++j;++k;
if(pattern[k]== pattern[j])
next[j]=next[k];
else
next[j]=k;
}
////这里是我加的显示部分
// for(int i=0;i<j;i++)
//{
// cout<<next[i];
//}
//cout<<endl;
}
下面是我写的KMP模式匹配程序，各位可以用他验证。记得加入上面的函数
#include <iostream.h>
#include <string.h>
int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='#CONTENT#' || Text[0]=='#CONTENT#' )//
return -1;//空指针或空串，返回-1。
int len=0;
const char * c=Pattern;
while(*c++!='#CONTENT#')//移动指针比移动下标快。
{
++len;//字符串长度。
}
int *next=new int[len+1];
get_nextval(Pattern,next);//求Pattern的next函数值
int index=0,i=0,j=0;
while(Text[i]!='#CONTENT#' && Pattern[j]!='#CONTENT#' )
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}//while
delete []next;
if(Pattern[j]=='#CONTENT#')
return index;// 匹配成功
else
return -1;
}
int main()//abCabCad
{
char* text="bababCabCadcaabcaababcbaaaabaaacababcaabc";
char*pattern="adCadCad";
//getNext(pattern,n);
//get_nextval(pattern,n);
cout<<KMP(text,pattern)<<endl;
return 0;
}
五．其他表示模式值的方法
上面那种串的模式值表示方法是最优秀的表示方法，从串的模式值我们可以得到很多信息，以下称为第一种表示方法。第二种表示方法，虽然也定义next[0]= -1,但后面绝不会出现 -1，除了next[0]，其他模式值next[j]=k(0≤k<j)的意义可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同，这里并不要求T[j] != T[k]。其实next[0]也可以定义为0（后面给出的求串的模式值的函数和串的模式匹配的函数，是next[0]=0的），这样，next[j]=k(0≤k<j)的意义都可以简单看成是：下标为j的字符的前面最多k个字符与开始的k个字符相同。第三种表示方法是第一种表示方法的变形，即按第一种方法得到的模式值，每个值分别加1，就得到第三种表示方法。第三种表示方法，我是从论坛上看到的，没看到详细解释，我估计是为那些这样的编程语言准备的：数组的下标从1开始而不是0。
下面给出几种方法的例子：
表一。
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
T | a | b | a | b | c | a | a | b | c |
(1) next | -1 | 0 | -1 | 0 | 2 | -1 | 1 | 0 | 2 |
(2) next | -1 | 0 | 0 | 1 | 2 | 0 | 1 | 1 | 2 |
(3) next | 0 | 1 | 0 | 1 | 3 | 0 | 2 | 1 | 3 |
第三种表示方法,在我看来，意义不是那么明了，不再讨论。
表二。
下标 | 0 | 1 | 2 | 3 | 4 |
T | a | b | c | a | c |
(1)next | -1 | 0 | 0 | -1 | 1 |
(2)next | -1 | 0 | 0 | 0 | 1 |
表三。
下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
T | a | d | C | a | d | C | a | d |
(1)next | -1 | 0 | 0 | -1 | 0 | 0 | -1 | 0 |
(2)next | -1 | 0 | 0 | 0 | 1 | 2 | 3 | 4 |
对比串的模式值第一种表示方法和第二种表示方法，看表一：
第一种表示方法next[2]= -1,表示T[2]=T[0]，且T[2-1] !=T[0]
第二种表示方法next[2]= 0,表示T[2-1] !=T[0],但并不管T[0] 和T[2]相不相等。
第一种表示方法next[3]= 0,表示虽然T[2]=T[0]，但T[1] ==T[3]
第二种表示方法next[3]= 1,表示T[2] =T[0],他并不管T[1] 和T[3]相不相等。
第一种表示方法next[5]= -1,表示T[5]=T[0]，且T[4] !=T[0]，T[3]T[4] !=T[0]T[1]，T[2]T[3]T[4] !=T[0]T[1]T[2]
第二种表示方法next[5]= 0,表示T[4] !=T[0]，T[3]T[4] !=T[0]T[1] ，T[2]T[3]T[4] !=T[0]T[1]T[2]，但并不管T[0] 和T[5]相不相等。换句话说：就算T[5]==’x’,或 T[5]==’y’,T[5]==’9’,也有next[5]= 0 。
从这里我们可以看到：串的模式值第一种表示方法能表示更多的信息，第二种表示方法更单纯，不容易搞错。当然，用第一种表示方法写出的模式匹配函数效率更高。比如说，在串S=“adCadCBdadCadCad 9876543”中匹配串T=“adCadCad”, 用第一种表示方法写出的模式匹配函数,当比较到S[6] != T[6] 时，取next[6]= -1（表三）,它可以表示这样许多信息： S[3]S[4]S[5]==T[3]T[4]T[5]==T[0]T[1]T[2]，而S[6] != T[6]，T[6]==T[3]==T[0]，所以S[6] != T[0],接下来比较S[7]和T[0]吧。如果用第二种表示方法写出的模式匹配函数,当比较到S[6] != T[6] 时，取next[6]= 3（表三）,它只能表示：S[3]S[4]S[5]== T[3]T[4]T[5]==T[0]T[1]T[2]，但不能确定T[6]与T[3]相不相等，所以，接下来比较S[6]和T[3];又不相等，取next[3]= 0，它表示S[3]S[4]S[5]== T[0]T[1]T[2]，但不会确定T[3]与T[0]相不相等，即S[6]和T[0] 相不相等，所以接下来比较S[6]和T[0]，确定它们不相等，然后才会比较S[7]和T[0]。是不是比用第一种表示方法写出的模式匹配函数多绕了几个弯。
为什么，在讲明第一种表示方法后，还要讲没有第一种表示方法好的第二种表示方法？原因是：最开始，我看严蔚敏的一个讲座，她给出的模式值表示方法是我这里的第二种表示方法，如图：
她说：“next 函数值的含义是：当出现S[i] !=T[j]时，下一次的比较应该在S[i]和T[next[j]] 之间进行。”虽简洁，但不明了，反复几遍也没明白为什么。而她给出的算法求出的模式值是我这里说的第一种表示方法next值，就是前面的get_nextval()函数。匹配算法也是有瑕疵的。于是我在这里发帖说她错了：
http://community.csdn.net/Expert/topic/4413/4413398.xml?temp=.2027246
现在看来，她没有错，不过有张冠李戴之嫌。我不知道，是否有人第一次学到这里，不参考其他资料和明白人讲解的情况下，就能搞懂这个算法（我的意思是不仅是算法的大致思想，而是为什么定义和例子中next[j]=k(0≤k<j)，而算法中next[j]=k(-1≤k<j)）。凭良心说：光看这个讲座，我就对这个教受十分敬佩，不仅讲课讲得好，声音悦耳，而且这门课讲得层次分明，恰到好处。在KMP这个问题上出了点小差错，可能是编书的时候，在这本书上抄下了例子，在那本书上抄下了算法，结果不怎么对得上号。因为我没找到原书，而据有的网友说，书上已不是这样，也许吧。说起来，教授们研究的问题比这个高深不知多少倍，哪有时间推演这个小算法呢。总之，瑕不掩玉。
书归正传，下面给出我写的求第二种表示方法表示的模式值的函数,为了从S的任何位置开始匹配T，“当出现S[i] !=T[j]时，下一次的比较应该在S[i]和T[next[j]] 之间进行。” 定义next[0]=0 。
void myget_nextval(const char *T, int next[])
{
// 求模式串T的next函数值（第二种表示方法）并存入数组 next。
int j = 1, k = 0;
next[0] = 0;
while ( T[j] != '#CONTENT#' )
{
if(T[j] == T[k])
{
next[j] = k;
++j; ++k;
}
else if(T[j] != T[0])
{
next[j] = k;
++j;
k=0;
}
else
{
next[j] = k;
++j;
k=1;
}
}//while
for(int i=0;i<j;i++)
{
cout<<next[i];
}
cout<<endl;
}// myget_nextval
下面是模式值使用第二种表示方法的匹配函数（next[0]=0）
int my_KMP(char *S, char *T, int pos)
{
int i = pos, j = 0;//pos(S 的下标0≤pos<StrLength(S))
while ( S[i] != '#CONTENT#' && T[j] != '#CONTENT#' )
{
if (S[i] == T[j] )
{
++i;
++j; // 继续比较后继字符
}
else // a b a b c a a b c
// 0 0 0 1 2 0 1 1 2
{ //-1 0 -1 0 2 -1 1 0 2
i++;
j = next[j]; /*当出现S[i] !=T[j]时，
下一次的比较应该在S[i]和T[next[j]] 之间进行。要求next[0]=0。
在这两个简单示范函数间使用全局数组next[]传值。*/
}
}//while
if ( T[j] == '#CONTENT#' )
return (i-j); // 匹配成功
else
return -1;
} // my_KMP
六．后话--KMP的历史
[这段话是抄的]
Cook于1970年证明的一个理论得到，任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题，也可以使用一个实际的计算机（更精确的说，使用一个随机存取机）在与问题规模对应的时间内解决。特别地，这个理论暗示存在着一个算法可以在大约m+n的时间内解决模式匹配问题，这里m和n分别是存储文本和模式串数组的最大索引。Knuth 和Pratt努力地重建了 Cook的证明，由此创建了这个模式匹配算法。大概是同一时间，Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是所有的算法都是“灵光一现”中被发现的，而理论化的计算机科学确实 在一些时候会应用到实际的应用中。
Zoj3059
Richard Lu 发表于 2010-12-20 14:39:32
// Zoj3059.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <deque>
#include <iostream>
#include <set>
using namespace std;
struct Status
{
int x;
int y;
int t;
int n;
bool operator==(Status&lo)
{
return x==lo.x && y == lo.y && t == lo.t && n == lo.n;
}
bool operator<(const Status&lo)const
{
return (x+y)< (lo.x+lo.y);
}
friend ostream& operator<<(ostream&,const Status&);
};
template <typename T>
class StatusLess : public less<T>
{
public:
virtual bool operator()(const T& t1, const T& t2) const
{
return t1< t2;
}
};
set<Status,StatusLess<Status>> visited;
int cube[7][4] = {{0,0,0,0},
{2,3,5,6},
{1,6,4,3},
{1,2,4,5},
{2,6,5,3},
{1,3,4,6},
{1,5,4,2}
};
int getLeftFace(int top, int north)
{
for (int ii = 0; ii< 4;ii++)
{
if (cube[top][ii]==north)
return cube[top][(ii+3)%4];
}
return -1;
}
int getRightFace(int top, int north)
{
for(int ii = 0; ii < 4; ii++)
{
if (cube[top][ii]==north)
return cube[top][(ii+1)%4];
}
return -1;
}
int getBottomFace(int top, int )
{
int bottom = top + 3;
return bottom > 6 ? bottom%6: bottom;
}
int getBackFace(int , int north)
{
int south = north + 3;
return south > 6 ? south%6: south;
}
ostream& operator <<(ostream& out, Status& lo)
{
out << "(" << lo.x <<","<< lo.y<<") " << "(" <<lo.t <<","<<lo.n <<")";
return out;
}
Status roll(int orient, Status& original)//left 0, right 1, front 2, back 3
{
Status result;
switch(orient)
{
case 0:
{
result.x = original.x-1;
result.y = original.y;
result.t = getRightFace(original.t, original.n);
result.n = original.n;
break;
}
case 1:
{
result.x = original.x+1;
result.y = original.y;
result.t = getLeftFace(original.t, original.n);
result.n = original.n;
break;
}
case 2:
{
result.x = original.x;
result.y = original.y+1;
result.t = getBackFace(original.t, original.n);
result.n = original.t;
break;
}
case 3:
{
result.x = original.x;
result.y = original.y-1;
result.t = original.n;
result.n = getBottomFace(original.t, original.n);
break;
}
default: break;
}
return result;
}
deque<Status> queue;
void bfs(Status& start, Status& end)
{
while(!queue.empty())
{
Status now = queue.front();
if (visited.find(now)!= visited.end())
{
queue.pop_front();
continue;
}
visited.insert(now);
queue.pop_front();
for (int ii = 0; ii < 4; ii++)
{
Status newS = roll(ii,now);
cout << now << " " << ii << " " << newS << endl;
queue.push_back(newS);
if (newS == end)
{
return;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Status start,end;
start.x = 0;
start.y = 0;
start.t = 1;
start.n = 2;
end.x = 1;
end.y = 1;
end.t = 5;
end.n = 6;
queue.push_back(start);
bfs(start,end);
return 0;
}
Mio C220破解问题
Richard Lu 发表于 2010-10-09 13:12:08
买HRV的时候正碰上通用在搞活动，送了个车载的GPS导航仪。型号是Mio C220，看到说明是Windows CE的内核，以前都没有摆弄过PDA，这次有条件了，故在网上搜索一把，发现Mio还是有些破解方法的。还有在Mio上安装别的导航软件的方法。
下面是在Mio C220上安装城际通3.0破解版（别问我城际通是什么，我对这个也是半桶水）的方法，不过里面有些下载地址似乎下不下来。这一部分我还没有试验过，因为没有1G的SD卡，也就无法试验是否真实可用了。
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
VV送的Mio C220上安装城际通3.0 PJ版成功！ 经过多次测试，终于在VV送的Mio C220上安装城际通3.0 PJ版成功！试用了（目前还没有路测，只做了了模拟导航）几次，除了偶尔会出现“非法*作”外，基本上还比较稳定，城际通的电子警察提示还是很有用的，但个人感觉地图没有原机安装的道道通新，信息也没有那么详细。
安装步骤：
1 下载PJ后的Mio C220文件传输工具，解压到电脑的任意文件夹。该工具可以在C220（包括其所有系统目录）和电脑之间传递文件。C220自带的传输工具是看不到C220的*作系统目录的，所以该工具是在C220上安装其它系统的关键。
2 下载城际通的3020-3109版本，并下载其对应PJ文件Navi.exe，注意我们的C220的GPS参数为COM2 - 4800BPS
如果不愿意去搜索，您在这里可以下载（510M左右）。里面的Navi.exe已经是PJ并对应COM2-4800BPS的了。
3 准备好至少1G的SD卡，在电脑上格式化成FAT格式。
4 把下载的CJT2030-3109全部解压到SD卡上，使Navi为根目录下的第一级子目录
5 因为在C220上直接使用上述CJT版本会出现“拷贝语音文件失败”的错误使程序无法运行，所以需要修改一下刚拷到SD卡上的Navi目录的Navi.exe文件，用HEX编辑工具（如UltraEdit）修改:
将 0xd3670 位置处一字节更改为 E8
. 将 0xd368c 位置开始的连续四字节一次更改为 01 00 A0 E3
如果你不想自己修改，也可以在这里下载我已经改过的文件，把它解压后覆盖到SD卡的Navi目录。
6 将SD卡插入C220中，在电脑上安装C220随带的驱动程序，用USB电缆连接C220和电脑，C220开机
7 在电脑上启动第一步下载的传输程序 Transfer_Mio_C250，在程序的右边可以看到C220里面的文件，和C220自带的文件传输程序看到的一样，我们需要进入C220的系统目录，请按如下步骤*作：
在随便双击某一个目录，可以看到右边的窗口内出现返回上级目录的箭头，双击这个箭头，就可以进入C220的上级目录，继续双击出现的“上级目录”箭头，就可以看到C220的根目录了。在其中可以看到Windows、Storage Card等等PDA上的各种目录了。
8 双击Windows目录，进入C220的Windows目录，在其中寻找ppath.txt，可以把它传输到左边（电脑中的目录），然后在电脑中修改该文件，把原来的;[Picture]\Windows\PictureViewer.exe一行改为[Picture]\Storage Card\Navi\Navi.exe（如下所示）。这样我们将把C220开机后显示的最后一个图标（图片浏览）的功能更改为启动城际通。如果你想改到其它图标或新建图标，修改这个文件即可。
;MainProgram=5,SubProgram=0,MainIcon=5,SubIcon=0,MainString=5,SubString=0
;IconPath=\Windows\
#Program position
[Miomap]\My Flash Disk\MioMap\MioMap\MioMap.exe
[Miomap]\My Flash Disk\MioMap\MioMap\MioMap.exe
[MP3]\Windows\MP3Player.exe
[Setting]\Windows\MioUtility.exe
[Video]\Windows\VideoPlayer.exe
[Picture]\Storage Card\Navi\Navi.exe
;[Picture]\Windows\PictureViewer.exe
#Icon coordinate
(10){x=201,y=17,w=110,h=111,shape=1}
(11){x=13,y=43,w=82,h=80,shape=1}
(12){x=51,y=140,w=82,h=80,shape=1}
(13){x=104,y=43,w=82,h=80,shape=1}
(14){x=141,y=140,w=82,h=80,shape=1}
#String coordinate
<10>{x=203,y=132,w=110,h=15}
<11>{x=13,y=126,w=82,h=15}
<12>{x=51,y=223,w=82,h=15}
<13>{x=104,y=126,w=82,h=15}
<14>{x=141,y=223,w=82,h=15}
9 将修改好的PPath.txt文件重新传回C220的windows目录，覆盖原来的文件。
10 关闭文件传输工具，点击C220上的最后一个图标试试，看看是不是已经可以进入城际通了呢！
如果不可以，请重起C220（热启动）再试试。
注意，如果不小心冷启动了C220，则其最后一个图标就会还原到原始设置（指向图片浏览功能）。这时候请您用上述的文件传输工具把修改好的PPath.txt重新传输到C220的windows目录就可以了。
以上方法，已经测试成功。VV送的GPS也可以一机多图了。凯利德等按照上述方法应该可以同样安装。
主要需要注意3点：1 C220的GPS参数是COM2-4800
2 一定要使用PJ后的文件传输工具
3 修改PPath.txt文件
另外，上面安装的城际通可以图形提示电子警察的位置，但没有声音提示。请下载语音文件 解压覆盖到SD卡的Navi\resource目录就可以了
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
此外在网上有Mio C220的破解，可以破解出Mio的Windows CE Core出来，我照做了一遍，初步发现不错，但是还有不少困惑。好像原来是一个意大利网站，有人贴了E文的说明，如下：
Here is the english read me.txt file for using the script. You will need to download the TRANSFER MIO C250 Hack file and the script files first from the link that kturley provided.
** Application manager for Mio DigiWalker C250 ***
It's a collection of applications for a visual and accessibility interface upgrade of the MioMap DigiWalker C250 model. An algorithm is also provided for an automatic interface recover in case of a complete reset (hard reset).
The installation is not particulary hard if the detailed instructions are followed:
1. First make a "hard reset" (press the start button for at least 6 seconds) and restart the device without pressing any more button.
2. Launch "Mio Transfer Hack C250" (watch out, not "Mio Transfer Hack"!!!) and in case a "\My Flash Disk\Script" directory is present, DELETE it.
3. Rename "\My Flash Disk\MioMap\MioMap" directory into "MioMap2", so that the directory tree becomes "\My Flash Disk\MioMap\MioMap2".
4. Create a directory named "MioMap" in the path "\My Flash Disk\MioMap\Miomap" so that in place of the first directory "MioMap" there are now two directories, "MioMap" and "MioMap2". In the "MioMap2" directory are located the navigator original files --> DON'T TOUCH ANYTHING HERE. Ending this step this structure has to be present:
My Flash Disk
|
|MioMap
|
|MioMap <-- Files needed for the unlocking
|MioMap2 <-- Original files
Now copy the "MioMap" directory files of the compressed archive in the "MioMap" directory just created. (Watch out it's the second directory "MioMap"!!!).
5. Create a "Script" directory in the "\My Flash Disk" directory and copy the "Script" directory files [of the compressed archive] in this one [just created], so that the directory tree results like is shown:
My Flash Disk
|
|Script <-- Files
6. When all files are copied, close "Mio Transfer Hack C250" pressing the EXIT button.
7. MAKE A HARD RESET.
8. After turning on the device, press on "MioMap". A file manager will open. We have to go to "\My Flash Disk\MioMap\MioMap" directory and launch the "AUTOPATCHER.exe" file. An information window will open saying the system has been recalled. Press OK and the system will restart.
9. After the restart, the application interface will be launched except if a memory card with a "77\" directory and an "autorun.exe" file is present. In that case, after the restart THAT file will be launched. This is useful if we want to try some applications which have to be renamed into "autorun.exe". If we don't want this file to be executed, take off the memory card and restart.
破解用的脚本在：http://www.megaupload.com/?d=RBGU1JD2，非常不好下。
随后又有人跟帖说该破解并不是真正意义上的破解，原帖在此：http://www.gpspassion.com/forumsen/topic.asp?TOPIC_ID=84734
对此我产生了不少兴趣，跟进中。
全球最出色的4个毕业典礼演讲
Richard Lu 发表于 2010-09-10 12:09:14
乔布斯(Steve Jobs)在斯坦福毕业典礼上的演讲
杰夫·贝佐斯(Jeff Bezos)在普林斯顿(Princeton)毕业典礼上的演讲
JK罗琳在哈佛大学毕业典礼上的演讲
Oprah(奥普拉)在斯坦福2008年毕业典礼上的演讲
谷歌创始人拉里·佩奇密歇根大学毕业典礼演讲
Ellen DeGeneres在纽奥良大学的毕业典礼演讲:
比尔·盖茨哈佛毕业演讲
http://www.colorfulcloud.com/best-four-commencement-speech.html