sunday算法解析

Question

public class SUNDAY{
public int QfindChr(string str, string Sfind)
{
int str_length = 0;
int fin_length = 0;

int find_count = 0;
int start = 0;
int moveNum = 0;

if (str.Length < Sfind.Length)
{
return find_count;
}

str_length = str.Length;
fin_length = Sfind.Length;

while (start + fin_length <= str_length)
{
moveNum++;
bool isfind = false;//是否在这次移动中找到
string s_temp = str.Substring(start, fin_length);
if (s_temp == Sfind)
{ find_count++; start = start + fin_length; isfind= true; }
if (isfind == false)//如果没找到计算下次移动位置
{
int forwardPos = QfindPos(str, Sfind, start, fin_length);
start = forwardPos;
}
}
return find_count;
}

public int QfindPos(string str, string find, int pos, int fin_length)
{
int returnPos = str.Length;
char[] Schr = str.ToCharArray();
char[] Sfin = find.ToCharArray();
if ((pos + fin_length) < str.Length)
{
char chrFind = Schr[pos + fin_length];//要找的字符
if (fin_length >= 1)
{
if (find.LastIndexOf(chrFind) > -1)
{
returnPos = pos + fin_length - find.LastIndexOf(chrFind);
}
else
{
returnPos = pos + fin_length + 1;
}
}
}
return returnPos;
}
}
谁能解释一下第二个函数的具体流程呀谢谢 仅限于这个sunday算法

Answer 1

例如我们要在"substring searching algorithm"查找"search"，刚开始时，把子
串与文本左边对齐，
substring searching algorithm
search
^
结果在第二个字符处发现不匹配，于是要把子串往后移动。但是该移动多少呢？这
就是各种算法各显神通的地方了，最简单的做法是移动一个字符位置；KMP是利用
已经匹配部分的信息来移动；BM算法是做反向比较，并根据已经匹配的部分来确定
移动量。这里要介绍的方法是看紧跟在当前子串之后的那个字符（上图中的'i'。
显然，不管移动多少，这个字符是肯定要参加下一步的比较的，也就是说，如果下
一步匹配到了，这个字符必须在子串内。所以，可以移动子串，使子串中的最右边
的这个字符与它对齐。现在子串'search'中并不存在'i'，则说明可以直接跳过一
大片，从'i'之后的那个字符开始作下一步的比较，如下图：
substring searching algorithm
search
^
比较的结果，第一个字符就不匹配，再看子串后面的那个字符，是'r',它在子串中
出现在倒数第三位，于是把子串向前移动三位，使两个'r'对齐，如下：
substring searching algorithm
search

Answer 2

答： int returnPos = str.Length;//存储str字符串的长度；
char[] Schr = str.ToCharArray();//将字符串str转化为字符数组（用数组存储）；
char[] Sfin = find.ToCharArray();//同上
if ((pos + fin_length) < str.Length)//判断此时的位置加上find字符串的长度是否还在str字符串范围内
{
char chrFind = Schr[pos + fin_length];//要找的字符
if (fin_length >= 1)
{
if (find.LastIndexOf(chrFind) > -1)//大于-1表示找到了要找的chrFind字符
{
returnPos = pos + fin_length - find.LastIndexOf(chrFind);//find.LastIndexOf(chrFind)此函数返回一个整数，此整数是发现字符chrFind的位置
}
else
{
returnPos = pos + fin_length + 1;//如果在字符串中找不到要找的字符，就去找下一个位置，但这个位置并不是下一个字符的位置，而是fing字符串长度（fing_length）个字符的位置。
}
}
}
return returnPos;
}