初级应用

  选择美丽的界面享受工作

虽然不能以貌取人，但似乎从来没有人责备以貌取软件的。SI的华丽界面，绝对符合现代花花世界的人的审美趣味。在SI中，我们可以轻松地把各种类型关键字、变量、标志符、函数、宏、注释等定义为不同的颜色和显示方式(正体或斜体、加粗或正常、加下划线、放大显示等)，总有一种方式能让我们一眼就能分辨出这个标识是什么。

  字体选择

在SI中样式是可以被继承，如果要从根本上改变字体，最简单的方式就是直接修改根样式中的字体，因为其它样式都会由此继承而来。选择Options/Document Options页面内的Font Options中的Screen Fonts字体，即可改变根样式中的字体。SI中的默认配置为Verdana字体，是一种非等宽字体 ² ，为了使编写的代码在各种编辑器中看起来都有良好的对齐效果，这里强烈建议使用等宽字体，Courier、New Courier和宋体等都是较好的选择。

  颜色定义

毕竟这是见仁见智的东西，所以从来没有统一的标准³。很多人并不喜欢SI提供的默认配置，那么我们就改吧。选择Options/Style Properties页面，就可以在其中修改所有样式了。选择等号(=)表示继承Parent Style，也可以选择Pick(或者ON/OFF等)去配置一个新值。这完全视乎个人喜好。

  标识符样式选择

在与 颜色定义 一节同样的界面内即可完成此项配置。

  背景色选择

在希望要改变背景色的窗口点击鼠标右键(假定使用的是右手鼠标 ⁴)，选择上下文菜单的 xxx Window Properties项，然后点击弹出窗口的Back Color按钮，即可修改该窗口背景色。对于SI的源码主窗口，只需选择上下文菜单的Special Window Color项即可完成背景色修改。

  配置合理的默认值高效工作

  使用合理的缩进

我始终认为最容易获得认同的是关于这个选项的配置了。选择Options/Document Options页面，点击其内的Auto Indent按钮，在弹出的Auto Indenting窗口中，默认配置为 Auto Indent Type选择Smart，且勾选了Smart Indent Options中的两个可选项，这样得到的默认缩进效果为

    while (1)
        {
        I
        }
 
 

每次都要手工去调整其缩进，其实只要把两个勾选项去掉，就可以得到

    while (1)
    {
        I
    }
 
 

何乐而不为呢？

  显示坐标

通常情况下在窗口状态栏左下方，最会显示当前光标所在行列信息，但我总觉得不够明显，于是通常我们作如下配置：

选择Options/Document Options页面，勾选其中的Show line numbers。同时勾选其中的Show right margin，我们就可显示一条右边界，随时提醒我们是否该行代码写得过长了。

  创建便捷的快捷键快乐工作

  几个较常用的快捷键

默认情况下，SI已经定义了很多非常实用的快捷键：

• F5
  指定行号，实现行跳转，在遇到编译错误的时候，能特别方便的找到出错行。
• Shift+F8
  高亮显示指定标识，快速浏览标识的使用情况。
• Ctrl+鼠标点击标识
  直接跳转至标识定义处。
• Ctrl+F
  本文件内查找。
• F3
  本文件查找结果的上一个。
• F4
  本文件查找结果的下一个。
• F7
  打开Browse Project Symbols窗口，快速浏览工程内标识定义。
• Ctrl+M
  创建或查找书签，方便下次找回此位置。

  自定义快捷健

选择Options/Key Assignments，在弹出的Key Assignments窗口中可自由添加自己喜欢的快捷键。比较值得推荐的有如下几个快捷键定义：

• Edit: Drag Line Down
  光标当前行下移。
• Edit: Drag Line Up
  光标当前行下移。
• Edit: Join Lines
  当前行和下一行连接成一行。

  更多的快捷键

如果你正好对SI的Marco语言(下文将会介绍)有研究，那么还可以定义更多有用的快捷键，比如添加文件头、函数头、注释等(下文在介绍Marco语言时会介绍如何实现)。

  小技巧-中级应用

  查找与替换

在SI中支持多种查找及替换方式，除了上文提到的文件内查找外，还支持工程范围内查找、目录查找、指定多文件查找等等。

  查找

1.        Loopup References
我们最常用的一种查找方式是选择Search/Lookup References或按Ctrl+/组合键再或者鼠标点  R 按钮，在弹出的Loopup References窗口进行查找操作。

在Search Method中有四种可选的查找方式：Simple String、Regular Expression、 Keyword Expression和Look Up Reference。其中Simple String是最普通的查找方式，可以查找文件中出现的任意字符或字符，甚至可以查找 _upap || u 这样的字符串，但是在工程较大时，查找过程会较慢。

Regular Expression查找方式将在后面讲述正则表达时会介绍到，这里暂时按下不表。

Keyword Expression和Look Up Reference查找的结果基本相同，但是显示方式略有差异。这两种方式都是使用SI预先建立的数据库，查找起来速度相当快。但通常这种速度只对在查找标识符时有明显效果。对于像函数名，变量名等的查找，强烈建议使用这两种方式进行查找。

2.        Search Files
选择Search/Search Files或按Ctrl+Shift+F组合键，在弹出的Search Files窗口进行查找操作。

在File Name框中可以填入文件名或文件夹。注意当要查询的文件夹双包含子文件夹时，可以勾选Options中的Include Subdirectiories，实现对各层文件的递归搜索。

3.        Search Project
选择Search/Search Project，在弹出的Search Project窗口进行查找操作。操作与Loopup References几乎完全一致，它们各自保存上次搜索的配置。

  替换

1.        单文件替换
选择Search/Replace或按Ctrl+H组合键，在弹出的Replace窗口进行查找操作。在Search项目里勾选Selection则仅对当前选中的文档部分进行替换。另外如果勾选了Confirm Replacements则是逐个确认替换，否则会同时替换所有符合替换条件内容。

2.        多文件替换
选择Search/Replace Files或按Ctrl+Shift+H组合键，在弹出的Replace Files 窗口进行查找操作。除了增加New框(替换后的内容)外，其余均与Search Files窗口相同，可参照查找部分的说明进行操作。

  列操作

虽然开篇时就说过，SI的列操作功能比较弱，但不等于没有。先按下Alt键，接着就可用鼠标进行列选择，然后就可以删除指定的列。

  无名技巧

这里介绍一些小技巧，大多数情况下我们可以无视它们的存在。但如果我们知道这些，某些时候，会有效提高工作效率。

• Smart Rename
  在上下文件菜单中选Smart Rename或按Ctrl+'组合键，即可弹出Smart Rename窗口。它有很强大的功能，但最便捷的使用方式是更改函数内局部变量的名字，操作只作用于函数内部，速度非常快。
• Renumber
  使用Ctrl+R将弹出Renumber窗口，这个用于处理数字顺序排列的情况相当有效，比如数组下标。例如现有代码

    array[0] = 1;
    array[1] = 2;
    array[2] = 3;
 
 

现在要改为

    array[0] = 0;
    array[1] = 1;
    array[2] = 2;
    array[3] = 3;
 
 

当然可以一个个修改，但最快的方式是在array[0] = 1;之前添加array[0] = 0;，然后列选数组下标，使用Renumber功能以 0为起始值重填数值。

• Edit Condition
  很多代码尤其是驱动代码，当中有大量的预编译定义，以实现对不同硬件配置的支持。在阅读这样的代码时最痛苦的是不能简单判断程序实际执行的代码分枝。大量分枝同时存在，常常会混淆我们的视听。比如对于下面的代码：

    #ifdef DEV1
        
    #else
        
    #endif
 
 

如果确定我们当前分析的是DEV1的执行情况 ⁵，那么可以选择上下文件菜单的Edit Condition 选项，在弹出的Conditional Parsing窗口中把DEV1的值设置为True，那么 #ifdef DEV1就等价于#if 1了，相当注释掉了#else分枝的代码。反之，设置为Flase时，则注释掉#ifdef DEV1分枝的代码。

  学会偷懒-高级应用

  附录1-SI中正则表达式

由于在查找及替换中，经常会使用用正则表达式⁶，这里对SI的正则表达式进行简单介绍。

  通配符

正则表达式通配符总表：

  表达式中的组

在执行替换操作时，组将大有用武之地。正则表达式的各个部分可以用\(和\)进行分隔，分隔得到的每一项就是一个组。在进行替换时可通过组从匹配内容中抽取出特定串。在正则表达式中每个组都有一个编号，自左至右编号从1开始。

例如：abc\(xyx\)将能匹配 abcxyz ，此时组1就包含了 xyz 串。在进行替换操作时，就可以通过在替换后内容框中填入来取出这个字符串。推而广之，可以使用\<number>来取得组<number>所包含的串。

例如：当设定把\(abc\)\(xyz\)替换为的替换规则时，对于 abcxyz 被替换串，则组1包含 abc，组2包含 xyz，而替换后的内容定义为组2内容后跟组1内容()，因此将得到 xyzabc。

举个真实的使用例子，相信会增加大家的兴趣。有时为方便调试，代码中到处流浪着各种形式的mytrace调用

    mytrace("Create parameter list... ");
 
 

有时希望把它们全部注释掉，而有些时候又希望把它们全部恢复回来。这是个简单的例子，可以使用

    ^\(.*\)\(/\*\)\(.*mytrace.*\)\(\*/\)___FCKpd___6nbsp;==> 
 
 

把它们恢复回来，而使用

    ^\(.*\)\(mytrace\)\(.*\)___FCKpd___7nbsp;==> 
 
 

则完成把它们全部注释掉。

  附录2-SI中的宏语言

我始终认为这是SI中最有趣的部分，这是一种功能强大的编程语言，几乎可以实现在编程过程可能使用到的各种功能。

这里不准备对如何实用宏语言进行编程作介绍(可参阅SI帮助文档。)，只介绍如何使用已编好程序。为方便使用，我已把这些程序都集中放在utils.em文件中，下文就此文件进行论述。

该宏文件实现了一些在编码过程中可能会用到的功能, 如添加文件头、函数说明(使用时能自动添加文件名、函数名和当前日期)和宏定义，代码补全等。

使用说明：

1.        Project/Open Project...
打开Base工程(该工程一般在"我的文档/Source Insight/Projects/Base"中)；

2.        Project/Add and Remove Project Files...
加入宏文件(即utils.em)；

3.        Options/Menu Assignments
打开Menu Assignments窗口，在Command中输入Macro，选中要使用的宏，添加到合适的菜单中.

推荐使用的宏：InsFileHeader、InsFunHeader、InsHeaderDef、InsIfdef和AutoExpand (为代码自动补全功能，建议建快捷键)。

关于AutoExpand的举例说明， 当你输入了 switch 且光标正处于switch后面，运行该宏则会得到

    switch (###)
    {
    case
        break;
    default:
    }
 
 

对于InsFunHeader宏，如果有如下函数体

    int nOpenConfigFile(char *pchMemConfig, char *pchFlashConfig,
        int nSize, int nMode)
    {
        I
    }
 
 

光标在函数体内时运行该宏，那么将会在函数体上方得到

 
 

其中的函数名及编写日期自动按实际情况填充，T357串可通过修改utils.em文件，改成你需要的名字。

  附录3-推荐格式

所谓人各有志，这里就不说啦。

  结束

将ClearCase的常用功能集成到Source Insight中的方法如下：（在这里仅以CheckOut为例进行说明)
1，选择Option中的Custome Commands
2, 在弹出的对话框中的Command列表中选择Check Out(或者点击Add自己起一个好记的名字）
3，在Run命令行中添加如下命令（其他的命令请见末尾）：
"C:\Program Files\Rational\ClearCase\bin\cleartool" checkout -nc %f
其中，如果你使用的不是ClearCase的默认路径的话，就请改为自己指定的路径吧
4，在将Output多选框中得Capture Output和Control多选框中的Pause When Done都选中，这样才能看到命令执行的结果哦。
5，将命令加入菜单项，点击Menu，在Menu下拉框中选择Work等（随便选就是了，至于添入那个菜单项中就看个人喜好了）进行添加。
由于CC的操作都可以通过命令行来进行，所以其他开发工具也可以同理应用

 

 

#include <iostream>
using namespace std;

char squre[7][7];
int m, n;

bool solve(int blank, int i, int j)
{
 if(squre[i][j] == 'S' || squre[i][j] == 'X')
  return false;
 if(blank == 0)
  return true;
 if(i>=n || i<0 || j>=m || j<0)
  return false;

 squre[i][j] = 'X';

 if(solve(blank-1, i+1, j) || solve(blank-1, i-1, j) || solve(blank-1, i, j+1) || solve(blank-1, i, j-1))
  return true;

 squre[i][j] = '.';
 return false; 
}

int main()
{
 int blank;
 int i, j;
 while(cin>>n>>m)
 {
  if(m == 0 && n == 0)
   break;
  blank = 0;
  for(i=0; i<n; ++i)
  {
   for(j=0; j<m; ++j)
   {
    cin>>squre[i][j];
    if(squre[i][j] == '.')
     blank++;
   }
  }
  if(solve(blank, 0, 0))
   cout<<"YES"<<endl;
  else
   cout<<"NO"<<endl;
 }

 return 0;
}

//////////////写得太乱了。。。考虑的情况有点多。自己都写昏了，还是要DEBUG才找到原因

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

void getcb(int& c11, int& c12, int& c21, int& c22, int& b1, int& b2)
{

 c11 = c12 = c22 = c21 = b1 = b2 = 0;
 int num, i;
 char str[800];
 string word;
 istringstream strs;
 bool sub = false, eq = false;
 cin.getline(str, 800);
 cin.getline(str, 800);
 strs.str(str);

 while(!strs.eof())
 {
  strs>>word;
  switch(word[word.size() - 1])
  {
  case 'x':
   num = 0;
   if(word.size() == 1)
    num = 1;
   else if(word.size() == 2 && word[0] == '-')
    num = -1;
   else if(word[0] == '-')
   {
    for (i=1; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    num = -num;
    
   }
   else
   {
    for (i=0; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    
   }
   if(sub)
    num = -num;
   if(eq)
    num = -num;
   sub = false;
   c11 += num;
   break;
  case 'y':
   num = 0;
   if(word.size() == 1)
    num = 1;
   else if(word.size() == 2 && word[0] == '-')
    num = -1;
   else if(word[0] == '-')
   {
    for (i=1; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    num = -num;
    
   }
   else
   {
    for (i=0; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    
   }
   if(sub)
    num = -num;
   if(eq)
    num = -num;
   sub = false;
   c12 += num;
   break;
  case '-':
   sub = true;
   break;
  case '=':
   eq = true;
   break;
  case '+':
   break;
  default:
   num = 0;
   if(word[0] == '-')
   {
    for (i = 1; i<word.size(); ++i)
    {
     num = num * 10 + word[i] - 48;   
    }
    num = -num;
   }
   else
   {
    for (i = 0; i<word.size(); ++i)
    {
     num = num * 10 + word[i] - 48;   
    }
   }
   if(sub)
    num = -num;
   if(!eq)
    num = -num;
   sub = false;
   b1 += num;
   
  }
 }

 eq = false;
 sub = false;
 strs.clear();
 cin.getline(str, 800);
 strs.str(str); 
 while (!strs.eof())
 {
  strs>>word;
  switch(word[word.size() - 1])
  {
  case 'x':
   num = 0;
   if(word.size() == 1)
    num = 1;
   else if(word.size() == 2 && word[0] == '-')
    num = -1;
   else if(word[0] == '-')
   {
    for (i=1; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    num = -num;
    
   }
   else
   {
    for (i=0; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    
   }
   if(sub)
    num = -num;
   if(eq)
    num = -num;
   sub = false;
   c21 += num;
   break;
  case 'y':
   num = 0;
   if(word.size() == 1)
    num = 1;
   else if(word.size() == 2 && word[0] == '-')
    num = -1;
   else if(word[0] == '-')
   {
    for (i=1; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    num = -num;
    
   }
   else
   {
    for (i=0; i<word.size() - 1; i++)
    {
     num = num * 10 + word[i] - 48;
    }
    
   }
   if(sub)
    num = -num;
   if(eq)
    num = -num;
   sub = false;
   c22 += num;
   break;
  case '-':
   sub = true;
   break;
  case '=':
   eq = true;
  case '+':
   break;
  default:
   num = 0;
   if(word[0] == '-')
   {
    for (i = 1; i<word.size(); ++i)
    {
     num = num * 10 + word[i] - 48;   
    }
    num = -num;
   }
   else
   {
    for (i = 0; i<word.size(); ++i)
    {
     num = num * 10 + word[i] - 48;   
    }
   }
   if(sub)
    num = -num;
   if(!eq)
    num = -num;
   sub = false;
   b2 += num;
  }
 } 
}

int gcd(int a, int b)
{
 int r, t;
 if(a < b)
 {
  t = a; a = b; b = t;
 }

 r = a % b;

 while (r != 0)
 {
  a = b;
  b = r;
  r = a % b;
 }
 return b;
}

void print(int a, int b)
{
 int g;
 if(a == 0)
  cout<<0<<endl;
 else
 {
  if(a < 0 && b > 0)
  {
   a = - a;
   cout<<"-";
  }
  else if (a > 0 && b < 0)
  {
   b = -b;
   cout<<"-";
  }
  if(a % b == 0)
   cout<<a/b<<endl;
  else
  {
   g = gcd(a, b);
   cout<<a/g<<"/"<<b/g<<endl;
  }
 }
}

int main()
{
 int n;
 int c11, c12, c21, c22, b1, b2;
 cin>>n;
 for(int t = 0; t<n; ++t)
 {
  if(t != 0)
   cout<<endl;
  getcb(c11, c12, c21, c22, b1, b2);
  if (c11 == 0)
  {
   if (c12 == 0)
   {
    if(b1 != 0)
    {
     cout<<"don't know"<<endl<<"don't know"<<endl;
    }
    else if (c21 == 0 && c22 != 0)
    {
     cout<<"don't know"<<endl;
     print(b2, c22);
    }
    else if (c22 == 0)
    {
     print(b2, c21);
     cout<<"don't know"<<endl;
    }
    else
    {
     cout<<"don't know"<<endl<<"don't know"<<endl;
    }
   }
   else if(c11 * c22 - c12 * c21 == 0)
   {
    if(c22 != 0 && (b1/c12 != b2/c22) || c21 == 0 && c22 == 0 && b2 != 0)
     cout<<"don't know"<<endl<<"don't know"<<endl;
    else
    {
     cout<<"don't know"<<endl;
     print(b1, c12);
    }
   }
   else
   {
    print(c12*b2 - c22 * b1,c21 * c12);
    print(b1, c12);
   }
  }
  else if (c12 == 0)
  {
   if (c11 * c22 - c12 * c21 == 0)
   {
    if(c21 != 0 && (b1/c11 != b2/c21) ||  c21 == 0 && c22 == 0 && b2 != 0)
     cout<<"don't know"<<endl<<"don't know"<<endl;
    else
    {
     print(b1, c11);
     cout<<"don't know"<<endl;
    }
   }
   else
   {
    print(b1, c11);
    print(c11*b2 - c21*b1, c22*c11);
   }
  }
  else if (c21 == 0)
  {
   if (c22 == 0)
   {
    cout<<"don't know"<<endl<<"don't know"<<endl;
   }
   else if (c11 * c22 - c12 * c21 == 0)
   {
    cout<<"don't know"<<endl;
    print(b2, c22);
   }
   else
   {
    print(c22*b1 - c12*b2, c11*c22);
    print(b2, c22);
   }
  }
  else if (c22 == 0)
  {
   if (c11 * c22 - c12 * c21 == 0)
   {
    print(b2, c21);
    cout<<"don't know"<<endl;
   }
   else
   {
    print(b2, c21);
    print(c21*b1 - b2*c11, c12*c21);
   }
  }
  else if (c11 * c22 - c12 * c21 == 0)
  {
   cout<<"don't know"<<endl<<"don't know"<<endl;
  }
  else
  {
   print(b1*c22 - b2*c12, c11*c22 - c21*c12);
   print(c21*b1 - c11*b2, c21*c12 - c11*c22);
  }
 }
 return 0;
}

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] != '{post.abstract}'&& T[j] != '{post.abstract}')

if ( S[i+j] == T[j] )

j ++; // 继续比较后一字符

else

{

i ++; j = 0; // 重新开始新的一轮匹配

}

if ( T[j] == '{post.abstract}')

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下标增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*/] != '{post.abstract}' )

       {

              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]  !=  '{post.abstract}')

       {

              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]=='{post.abstract}'  ||  Text[0]=='{post.abstract}' )//

              return -1;//空指针或空串，返回-1。

       int len=0;

       const char * c=Pattern;

       while(*c++!='{post.abstract}')//移动指针比移动下标快。

       {    

              ++len;//字符串长度。

       }

       int *next=new int[len+1];

       get_nextval(Pattern,next);//求Pattern的next函数值

   

       int index=0,i=0,j=0;

       while(Text[i]!='{post.abstract}'  && Pattern[j]!='{post.abstract}' )

       {

              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]=='{post.abstract}')

              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] != '{post.abstract}' )

     {    

                   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] != '{post.abstract}' && T[j] != '{post.abstract}' )

{

    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] == '{post.abstract}' )

    return (i-j); // 匹配成功

else

     return -1;

} // my_KMP

 

 

六．后话--KMP的历史

[这段话是抄的]

Cook于1970年证明的一个理论得到，任何一个可以使用被称为下推自动机的计算机抽象模型来解决的问题，也可以使用一个实际的计算机（更精确的说，使用一个随机存取机）在与问题规模对应的时间内解决。特别地，这个理论暗示存在着一个算法可以在大约m+n的时间内解决模式匹配问题，这里m和n分别是存储文本和模式串数组的最大索引。Knuth 和Pratt努力地重建了 Cook的证明，由此创建了这个模式匹配算法。大概是同一时间，Morris在考虑设计一个文本编辑器的实际问题的过程中创建了差不多是同样的算法。这里可以看到并不是所有的算法都是“灵光一现”中被发现的，而理论化的计算机科学确实在一些时候会应用到实际的应用中。

opengl 4-5章
NEHE8-9课
C++11--12章
实现算法一个