pascal程序查病毒
发布网友
发布时间:2024-09-27 18:08
我来回答
共3个回答
热心网友
时间:2024-10-15 16:42
var st:string;
n,l,i,j,ans:longint;
function check:boolean;{判断是否是最长回文子串}
var k,t:longint;
begin
t:=i+j;
for k:=i to (t div 2) do
if(st[k]<>st[t-k])then exit(false);
exit(true);
end;
begin
assign(input,'D.in');
reset(input);
assign(output,'D.out');
rewrite(output);
readln(st);
n:=length(st);
ans:=1;{记录找到的最长回文子串的长度}
for i:=1to n do
for j:=i+1 to n do{枚举最长回文子串}
begin
l:=j-i+1;{记录最长回文子串的长度}
if(check)and(l>ans){找到更长的最长回文子串}then ans:=l;
end;
writeln(ans);
close(input);
close(output);
end.
这个算法的时间复杂度应该是O(n^3),应该还有更快的方法。不过n<=100这个算法完全不会超时。
其实好像也可以根据最长回文子串的长度来二分答案(如果存在一个最长回文子串,那么必然存在这样的回文子串,他的长度比最长回文子串小2*k,k=1,2,3……)不过这样就要考虑一下奇偶了,时间复杂度应该是O(log2,n*n^2)。你认真想一下吧!
var st:string;
n,l,i,j,ans:longint;
function check:boolean;{判断是否是最长回文子串}
var k,t:longint;
begin
t:=i+j;
for k:=i to (t div 2) do
if(st[k]<>st[t-k])then exit(false);
exit(true);
end;
begin
assign(input,'D.in');
reset(input);
assign(output,'D.out');
rewrite(output);
readln(st);
n:=length(st);
ans:=1;{记录找到的最长回文子串的长度}
for i:=1to n do
for j:=i+1 to n do{枚举最长回文子串}
begin
l:=j-i+1;{记录最长回文子串的长度}
if(check)and(l>ans){找到更长的最长回文子串}then ans:=l;
end;
writeln(ans);
close(input);
close(output);
end.
这个算法的时间复杂度应该是O(n^3),应该还有更快的方法。不过n<=100这个算法完全不会超时。
其实好像也可以根据最长回文子串的长度来二分答案(如果存在一个最长回文子串,那么必然存在这样的回文子串,他的长度比最长回文子串小2*k,k=1,2,3……)不过这样就要考虑一下奇偶了,时间复杂度应该是O(log2,n*n^2)。你认真想一下吧!
热心网友
时间:2024-10-15 16:42
用杀毒软件来查毒,很快就知道了,不用这么麻烦。
热心网友
时间:2024-10-15 16:43
var st:string;
n,l,i,j,ans:longint;
function check:boolean;{判断是否是最长回文子串}
var k,t:longint;
begin
t:=i+j;
for k:=i to (t div 2) do
if(st[k]<>st[t-k])then exit(false);
exit(true);
end;
begin
assign(input,'D.in');
reset(input);
assign(output,'D.out');
rewrite(output);
readln(st);
n:=length(st);
ans:=1;{记录找到的最长回文子串的长度}
for i:=1to n do
for j:=i+1 to n do{枚举最长回文子串}
begin
l:=j-i+1;{记录最长回文子串的长度}
if(check)and(l>ans){找到更长的最长回文子串}then ans:=l;
end;
writeln(ans);
close(input);
close(output);
end.
这个算法的时间复杂度应该是O(n^3),应该还有更快的方法。不过n<=100这个算法完全不会超时。
其实好像也可以根据最长回文子串的长度来二分答案(如果存在一个最长回文子串,那么必然存在这样的回文子串,他的长度比最长回文子串小2*k,k=1,2,3……)不过这样就要考虑一下奇偶了,时间复杂度应该是O(log2,n*n^2)。你认真想一下吧!