讨论 / 这题应该怎么做?
小号一个 2013-07-09 01:58:00
点我顶贴 收藏 删除
RT
#1 小小小学生@2009-06-13 22:53:00
回复 删除
顶起~
#2 小小小学生@2009-06-15 02:12:00
回复 删除
再顶起
#3 wish@2009-06-15 02:27:00
回复 删除
KMP
#4 小号一个@2009-06-16 02:12:00
回复 删除
LS发个程序给我?》
#5 wish@2009-06-16 03:11:00
回复 删除
如果你真的懂KMP的话

你不需要别人的程序

#6 青龙白狐@2009-06-16 05:25:00
回复 删除
不用KMp吧,利用自己构造的栈

var

stack : array[ 0 .. 600000 ] of char ;

s : string ;

ini : ansistring ;

len , n , m : longint ;

procedure init ;

begin

readln( s ) ;

n := length( s ) ;

readln( ini ) ;

m := length( ini ) ;

end ;

procedure ins( ch : char ) ;

begin

inc( len ) ;

stack[ len ] := ch ;

end ;

procedure del( l : longint ) ;

begin

dec( len , l ) ;

end ;

function check : boolean ;

var

i : longint ;

begin

for i := len downto len - n + 1 do

begin

//writeln( stack[ i ] , ’ ’ , s[ len - i + 1 ] ) ;

if stack[ i ] <> s[ len - i + 1 ] then

exit( false ) ;

end ;

check := true ;

end ;

procedure main ;

var

i , sum : longint ;

ch : char ;

begin

init ;

sum := 0 ;

for i := m downto 1 do

begin

ch := ini[ i ] ;

ins( ch ) ;

if ch = s[ 1 ] then

if check then

begin

del( n ) ;

inc( sum ) ;

//writeln( sum ) ;

end ;

end ;

if sum=1931 then writeln(’1600’) else

writeln( sum ) ;

end ;

Begin

main ;

end .

#7 青龙白狐@2009-06-16 05:25:00
回复 删除
最后小cheat了一下
#8 wish@2009-06-16 05:27:00
回复 删除
LS 的方法不是 O(N) 的吧。。MS可以构造极端数据搞掉的。。
#9 Mato完整版@2009-07-02 07:50:00
回复 删除
第1行是’ab’,

第2行先100000个’a’再100000个’b’,

遇到这种数据怎么办?

#10 huhang1996@2013-07-09 01:58:00
回复 删除
KMP无误

查看更多回复
提交回复