前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法模板——KMP字符串匹配

算法模板——KMP字符串匹配

作者头像
HansBug
发布2018-04-10 16:49:04
9240
发布2018-04-10 16:49:04
举报
文章被收录于专栏:HansBug's Lab

功能:输入一个原串,再输入N个待匹配串,在待匹配串中找出全部原串的起始位置

原理:KMP算法,其实这个东西已经包含了AC自动机的思想(fail指针/数组),只不过适用于单模板匹配,不过值得一提的是在单模板大量匹配待匹配串时,这个会有相当大的优势,AC自动机虽然好想一些,但是在这一类问题上的性价比就略低了

代码语言:javascript
复制
 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          begin
10               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 do
16          begin
17               readln(s2);
18               j:=0;
19               for i:=1 to length(s2) do
20                   begin
21                        inc(j);
22                        if s1[j]=s2[i] then
23                           begin
24                                if j=length(s1) then
25                                    begin
26                                         write(i-length(s1)+1,' ');
27                                         j:=a[j];
28                                    end;
29                           end
30                        else
31                            begin
32                                 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                    
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-02-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档