字符串匹配的算法问题 (100分)

还是感觉有些别扭，另外，Names中的每个值还是得要定长的，否则不好取Index

to: beta
是啊，用StrPas只是我心理上觉得安全一些：）

to: 爱元元的哥哥
用Hash表肯定是不错的选择，但是我想楼主觉得TStrings的开销都大，Hash表的开销也
不会比TStrings小多少的。

to:Adnil
既然Names要定长，Value要定长，还真不如合并到一个字符串里
另外，我觉得
type
TSearchRec = packed record
name: array[0..19] of Char;
value: array[0..99] of Char;
end;
var
aSearchs: array[0..999] of TSearchRec;
这样的aSearchs就是连续的存放Char的了，这样，你添加修改也很方便，查找也很快
（如果你觉得
for i := Low(aSearchs) to High(aSearchs) do
if aSearchs.name = searchstr then
不够快的话，因为知道了SizeOf(TSearchRec)，就可以自己编写类似Pos的函数了）

合并到一个字符串会导致搜索的时间增加，因为不需要搜索Value。

明天接受答案，有更好意见的朋友请踊跃发言 ：）

>>合并到一个字符串会导致搜索的时间增加，因为不需要搜索Value。
太简单了：将字符串匹配算法进行改进，改成“跳跃匹配”即可。实际上，只要能够保证
Names的元素长度相同，就可以使用“跳跃匹配”，只将Names合并即可，Values仍然使用数
组（即使Names元素长度不等，我们仍然可以通过在末尾补空格的方法使之等长）。

跳跃匹配算法大致思路：
SubStr: 'ab ,' (length:4)
Str: '123,4 ,aA*,ab ,def,' (length: StrCount*4)
//辅助变量
P1,P2,P01,P02,PStrEndChar;
Len,c:Integer;
//init:
Len:=Length(SubStr);
P01:=@SubStr[1];
P02:=@Str[1];
PStrEnd:=@Str[Length(Str)];
repeat
c=0
//匹配计数器清零
P1:=P01
//SubStr指针复位
P2:=P02
//头指针 -> 指针
Inc(P02,Len)
//完成头指针跳跃
while P1^=P2^ do //匹配
begin
Inc(c);
if c=Len then
break;
Inc(P1);
Inc(P2);
end;
if P02>=PStrEnd then //结尾判断
break;
until c=Len;
if c=Len then
Result:=(Integer(PC02)-Integer(PC01)) div Len //成功匹配，返回序号 (>=1)
else
Result:=0
//匹配失败，返回0

算法的平均时间复杂度仅为O(StrCount*K+SubStrLength)（注:K是一个介于1和SubStrLength
之间的系数，它反映了平均要经过多少次匹配才能判定匹配失败，eg:'abc'和'123'只要一
次比较，而'abc'和'abd'则要等到第三位才能发现它们并不匹配。我认为在一般情况下，K
的值应该在1到SubStrLength/3之间）。对于上面的例子字符串，我的算法只要进行8次比较
就可以得到结果。


楼主的意思我始终不明白：又要“尽可能的快”，又要“尽可能少占内存”（这还可以理
解），又强调“次数多不是很多，所以不想用高效容器”——？？！！——如果你只是准备
到隔壁房间打三五个来回，你有没有必要为了买什么跑鞋才能跑得更快而大伤脑经？？

又想到一个更快的方案：用Hash的Integer数组进行搜索，这样处理之后，时间复杂度中
的K始终为1，由于SubStr被Hash之后才进行搜索，时间复杂度和在一个Integer数组中搜索
指定整数值位置的复杂度相当——O(StrCount)。

另：由于采用“跳跃匹配”，作为分隔符的逗号已经没有用处了（因为跳跃不可能出现错
位的情况）。上面的例子可以被简化为： 'ab ' '1234 aA*ab def' ——比普通的字符串
匹配算法又节约了 StrCount+1 Byte的存储空间

>>合并到一个字符串会导致搜索的时间增加，因为不需要搜索Value。
怎么会呢？
当定长Name和Value的时候，根本不需要搜索Value
设Name 10,Value 20，则Inc(PChar,30)就到下一个了
to:creation-zy
定长Name本来就不需要分隔符的：）
用Hash那要先MakeHash，搜索字符串和Name也要处理，麻烦一些，不过速度肯定会快的
（我是怕麻烦的人，呵呵）


不过我也认为Names用Hash（定位时间短了），Values定长（定位之后可以直接取得Values）
肯定是效果比较好的：）
其实Values定长，真的可以用
type
TValue: array[0..99] of Char;
var
Values: array[0.999] of TValue;
来表达，这也是连续的空间，每个Value的末尾还都是#0，取Value方便（#0结束），
定位快速（连续空间，用Values效率应该也还可以，不会比自己增加指针慢的吧），
修改方便Values := 'test' 就可以了。

但使用整数数组来定位Names的话，这个数组是排序的好，还是不排序的好？
如果排序，搜索Names起来会可以用很高效的算法，但是插入新值，删除旧值的时候，Values
需要移动内存（要保证是连续的空间才能保证定位的高效）。
如果不排序，就不能用很高效的Names的定位算法了。
看来这就需要看楼主的需求了。

但是如果用整数数组，定位是要好得多，最起码不用比较Names了（开销比较大）

接受答案了！ 分数不多，大家见谅啊！

如果插入和删除操作比较多，那就用连表！