首页 > 代码库 > 算法模板——KMP字符串匹配
算法模板——KMP字符串匹配
功能：输入一个原串，再输入N个待匹配串，在待匹配串中找出全部原串的起始位置
原理：KMP算法，其实这个东西已经包含了AC自动机的思想（fail指针/数组），只不过适用于单模板匹配，不过值得一提的是在单模板大量匹配待匹配串时，这个会有相当大的优势，AC自动机虽然好想一些，但是在这一类问题上的性价比就略低了
1 var 2 i,j,k,l,m,n:longint; 3 a:array[0..100000] of longint; 4 s1,s2:ansistring; 5 begin 6 readln(s1); 7 a[1]:=0; 8 for i:=2 to length(s1) do 9 begin10 j:=a[i-1];11 while (j>0) and (s1[j+1]<>s1[i]) do j:=a[j];12 if s1[j+1]=s1[i] then a[i]:=j+1 else a[i]:=0;13 end;14 readln(n);15 for l:=1 to n do16 begin17 readln(s2);18 j:=0;19 for i:=1 to length(s2) do20 begin21 inc(j);22 if s1[j]=s2[i] then23 begin24 if j=length(s1) then25 begin26 write(i-length(s1)+1,‘ ‘);27 j:=a[j];28 end;29 end30 else31 begin32 j:=j-1;33 while (j>0) and (s1[j+1]<>s2[i]) do j:=a[j];34 if s1[j+1]=s2[i] then inc(j) else j:=0;35 end;36 end;37 writeln;38 end;39 readln;40 end.41
算法模板——KMP字符串匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。