取相同字串算法(300分)

  • 主题发起人 主题发起人 DNChen
  • 开始时间 开始时间
D

DNChen

Unregistered / Unconfirmed
GUEST, unregistred user!
比较两个字符串，将其中所想同的最长字符串返回
比如有两个字符串
a: a111111d
b: d111121d
最后返回1111。
 
我记得清华的数据结构教财力有一个这样的例子
 
我一个朋友搞压缩，改天帮你问问。
简单点的话，一个个比较，速度成问题。
 
得自己写过程了，没建国这样的算法。
 
相同的字符串是否要求位置也要一样？
 
字符传不长就自己一个一个来吧，以现在的cpu，算这个即使算法差一点都不会感觉到了
 
只见过字符串查找的算法，我试试看能否改进。
 
对了，我也记得那本书里有。

位置可以不同的。

请提供一个最高效率的算法，因为我所用的情况变化比较大，而且速度要求也比较高，最好让用户不觉得延迟，：）
 
呵呵,今天试了一下,写出来一段,反正我自己输了不少字符串测试都行的
就是找到的最长相同字符串会出现重复,比如:
a111111d
d111121d -> 1111,1111,1111
DNChen:满足你的要求吗?

{
a,b放置比较的两个字符串，无先后次序之分
c,d是工作字符串,r存放找出的所有相同字符串
maxlen指出相同字符串重的最大长度
思想: a固定不动,b从左向右依次与a比较
例: a='12345' b='345'
c ==12345==
b 345 -> d ---------
-----------
c ==12345==
b 345 -> d ---------
-----------
c ==12345==
b 345 -> d ---------
-----------
c ==12345==
b 345 -> d ---------
-----------
c ==12345==
b 345 -> d ----345--
-----------
c ==12345==
b 345 -> d ---------
-----------
c ==12345==
b 345 -> d ---------

form1有edit1,edit2,edit3三个文本框,一个button1按钮
}

procedure TForm1.Button1Click(Sender: TObject);
var
a,b,c,d:string;
i,j,k,la,lb,lc:integer;
r:array of string;
rp,maxlen:integer;
begin
rp:=0;
setlength(r,1);

a:=edit1.text;
b:=edit2.text;
la:=length(a);
lb:=length(b);
if (la=0) or (lb=0) then exit;
lc:=la+lb*2-2;

setlength(c,lc+1);
c:=stringofchar(' ',lc);
for i:=lb to la+lb-1 do
c:=a[i-lb+1];

for i:=1 to la+lb-1 do
begin
d:=stringofchar('-',lc);
for j:=1 to lb do
d[i+j-1]:=b[j];
for j:=1 to lc do
if c[j]=d[j] then d[j]:=c[j] else d[j]:='-';
//找出最多的一次匹配
k:=1;
repeat
if d[1]='-' then
d:=copy(d,2,length(d)-1)
else begin
k:=k+1;
if d[k]='-' then
begin
rp:=rp+1;
setlength(r,length(r)+1);
r[rp]:=copy(d,1,k-1);
d:=copy(d,k,length(d)-k+1);
k:=1;
end;
end;
until length(d)=0;
end;

maxlen:=0;
for i:=1 to length(r)-1 do
begin
if length(r)>maxlen then maxlen:=length(r);
end;
edit3.text:='';
if maxlen>0 then
for i:=1 to length(r)-1 do
if length(r)=maxlen then
edit3.text:=edit3.text+r+',';
end;
 
数据结构中的模式匹配算法
 
试试这个：
s1,s2 是你输入的字符串， length(s1) <= Length(s2)
find := False;
i := Length(s1);
repeat
for j := 1 to Length(s1) - i + 1 do
begin
temp := Copy(s1, j, i)
if Pos(temp, s2) > 0 then
begin
Find := True;
打印 temp;
end;
end;
Dec(i);
until Find or (i < 1);
 
忘说了，手头没有delphi， 没法测试。
 
function MaxLength(const a,b: String): String;
var
la,lb: Byte;
i, j: Byte;
s: String;
begin
la:=length(a);
lb:=length(b);
for i:=la downto 1 do
for j:=1 to la-i+1 do
begin
s:=copy(a,j,i);
if pos(b,s)>0 then
begin
Result:=s;
Exit
end
end;
Result:=''
end;
 
To OnlyD4:
两种是有一定区别的。必须在数据结构中的模式匹配算法的基础上改变一下以
适合上述要求！
 
非常复杂，要实现的功能非常有趣。
有一个软件，我放在http://www.keenvim.com/software/cmp.com上了。
你们去看看，要实现与这个软件一样的字串比较，就已经很不容易了。

但我想应该实现“不论位置，均可比对”，例：

ABCDOOOCDEFChiQQQQ
AOOOCDEFhiABCD
必须得到这样的结果：
ABCD<b>OOOCDEF</b>C<b>hi</b>QQQQ
A<b>OOOCDEF</b><b>hi</b>ABCD或者
<b>ABCD</b>OOOCDEFChiQQQQ
AOOOCDEFhi<b>ABCD

大家想想，能怎么做？ ^-^
 
要连续和最长吗?ABCD不是最长找出来干啥?
 
多人接受答案了。
 
您必须登录或注册才可回复。

Similar threads

Ray
[转]终于可以发布Delphi下收点OSGI精髓皮毛而设计的插件框架WisdomPluginFramework
回复
4
查看
4K
chlkuei
C
P
一个关于字符串的问题(70分)
回复
2
查看
157
PolinChen
P
B
能否由一个与某类属性名相同的字符串得到该属性值？(50分)
回复
14
查看
281
Beast
B
A
请看看这个问题，谢谢！(10分)
回复
7
查看
171
awfigsk
A
D
用什么函数来实现获取一字符串的任意位置的字符！ (50分)
回复
12
查看
247
lxn2philips
L
后退
顶部