主串模式——最常用的FPGA配置模式
1．配置单片FPGA
在主串模式下，由FPGA的CCLK管脚给PROM提供工作时钟，相应地PROM在CCLK 的上升沿提供将数据从D0管脚送到FPGA的DIN管脚。无论PROM芯片类型（即使其支持并行配置），都只利用其串行配置功能。例如Spartan3E单片FPGA的主串配置电路如图5-12所示。
图5-12 Soartan-3E主从模式配置电路
1）信号管脚说明
其中要注意3类管脚的连接方式：首先，模式选择管脚M[2:0]在配置过程中或者INIT_B变高时，必须设置为全0，当FPGA的输出管脚DONE变高后，模式配置管脚可以作为普通I/O管脚使用；其次，HSWAP管脚的输入电平在器件配置阶段必须保持不变，可以拉低使能FPGA所有I/O管脚的上拉电阻，也可以拉高去掉FPGA所有I/O管脚的上拉电阻，当FPGA配置完毕，输出信号DONE变高后，可以作为普通I/O管脚使用；最后，FPGA的DOUT管脚仅在多芯片配置时有效，在单芯片配置中悬空。
（1）对图5-12中FPGA芯片各个管脚的功能和配置进行简单介绍，如表5-5所示。
表5-5 主串模式下FPGA配置管脚说明
（2）必须要掌握从设备PROM的管脚信号。下面对图5-12中PROM芯片各个管脚的功能和配置进行简单介绍，如表5-6所列。
表5-6 主串模式下PROM配置管脚说明
2）配置电路的关键点
主串配置电路最关键的3点就是JTAG链的完整性、电源电压的设置以及CCLK 信号的考虑。只要这3步任何一个环节出现问题，都不能正确配置PROM芯片。
（1）JTAG链的完整性
FPGA和PROM芯片都有自身的JTAG接口电路，所谓的JTAG链完整性指的是将JTAG 连接器、FPGA、PROM的TMS、TCK连在一起，保证从JTAG连接器TDI到其TDO 之间，形成JTAG连接器的“TDI （TDI~TDO）（TDI~TDO） JTAG连接器TDO”的闭合回路，其中（TDI~TDO）为FPGA或者PROM芯片自身的一对输入、输出管脚。图5-12中配置电路的JTAG链从连接器的TDI到FPGA的TDI，再从FPGA的TDO到PROM的TDI，最后从PROM的TDO到连接器的TDO，形成了完整的JTAG链，FPGA芯片被称为链首芯片。也可以根据需要调换FPGA和PROM的位置，使PROM 成为链首芯片。
（2）电源适配性
如图5-13所示，由于FPGA和PROM要完成数据通信，二者的接口电平必须一致，即FPGA相应分组的管脚电压Vcco_2必须和PROM Vcco的输入电压大小一致，且理想值为2.5V，这是由于FPGA的PROG_B和DONE管脚由2.5V的Vccaux供电。此外，由于JTAG连接器的电压也由2.5V的Vccaux提供，因此PROM的VCCJ也必须为2.5V。因此，如果接口电压和参考电压不同，在配置阶段需要将相应分组的管脚电压和参考电压设置为一致；在配置完成后，再将其切换到用户所需的工作电压。当然，FPGA和PROM也可以自适应3.3V的I/O电平以及JTAG电平，但需要进行一定的改动，即添加几个外部限流电阻，如图5-13所示。在主串模式下，XCFxxS系列PROM的核电压必须为3.3V，XCFxxP系列PROM的核电压必须为1.8V。
图5-13 3.3V的JTAG配置电路示意图
图5-13中的RSER、RPAR这两个电阻要特别注意。首先，RSER= 68Ω将流入每个输入的电流限制到 9.5 mA；其次，N = 3三个输入的二极管导通，
RPAR = VCCAUX min/ NIIN = 2.375V/（3*9.5mA）
=83 Ω或 82 Ω（与标准值误差小于 5% 的电阻）
（3）CCLK的信号完整性
CCLK信号是JTAG配置数据传输的时钟信号，其信号完整性非常关键。FPGA配置电路刚开始以最低时钟工作，如果没有特别指定，将逐渐提高频率。CCLK信号是由FPGA内部产生的，对于不同的芯片和电平，其最大值如表5-7所示。
表5-7 不同PROM芯片的最大配置时钟频率
3）主串配置电路工作流程
一般FPGA芯片都有两个配置触发事件：上电复位以及软件复位。不同配置模式的工作流程基本是一致的，下面对整个过程进行详细说明。
（1）普通配置过程
当FPGA上电后，如果核电压、参考电压以及I/O电压正确，则进入配置模式。数据首先以TCK的速度通过JTAG连接器的TDI管脚，进入FPGA芯片的TDI管脚。然后再以同样的速率从FPGA的TDO管脚将配置数据送入PROM芯片的TDI管脚，此时PROM通过其TDO向JTAG连接器的TDO环回数据，构成完整的JTAG链；又由于FPGA芯片DONE信号为低（片选PROM芯片）、INIT_B输出电平为高（使能PROM数据输出管脚），PROM通过DO以CCLK的速率将配置数据送给FPGA。第三，FPGA开始接收配置数据，并完成CRC校验，若CRC校验通过，DONE信号管脚输出高电平；若CRC校验失败，DONE信号为低，配置过程失败，但此时FPGA并不给出任何指示，这时由于需要在DONE管脚上添加LED以输出提示信号。最后，PROM由于CE管脚输入为高，关闭数据输出管脚，清空地址计数器，进入休眠状态，配置结束。
（2）复位配置过程
当PROG_B处于低电平超过500ns时，会强制FPGA进入重配置阶段；当PROG_B
信号变高时，会清空FPGA配置存储器，并将DONE、INIT_B拉低。由于DONE信号和PROM芯片CE信号相连，PROM片选有效。CF信号有效，将PROM内部地址计数器清零。当清空FPGA配置存储器后，OE/RESET变高，地址累加器开始在CLK 的上升沿加1。FPGA配置结束后，DONE信号管脚输出高电平，PROM关闭数据输出管脚，清空地址计数器，进入休眠状态。复位配置的过程如图5-14所示。
图5-14 复位后FPGA配置阶段示意图
2．配置多片FPGA
多片FPGA的配置电路和单片的类似，但是多片FPGA之间有主（Master）、从（Slave）之分，且需要选择不同的配置模式。两片Spartan 3E系列FPGA的典型配置电路如图5-15所示，两片FPGA存在主、从地位之分。
图5-15 主从模式下两片FPGA的配置电路
如果系统中有更多的FPGA芯片，只需要在后面继续添加即可，即从链首FPGA
获得CCLK，将芯片TCK、TMS和JTAG连接器的TCK、TMS连接在一起，最后把上一级FPGA的TDO连接到本地TDI，并将本地TDO和JTAG连接器的TDO连在一起，构成完整的JTAG链。当链首FPGA完成配置后，将利用其DOUT管脚为在CCLK
的下降沿为后续芯片传送配置数据，而其自身在CCLK的上升沿从PROM读取配置
数据。注意：除了链首FPGA的模式选择信号M[2:0]=3’b000外，其余FPGA的模式选择信号M[2:0]=3’b111。
如果多片相同FPGA配置相同的数据，可以采用图5-16所示的配置电路。
图5-16 配置数据相同的多片相同FPGA的配置电路
5.3.2 SPI串行Flash配置模式
1．SPI串行配置介绍
串行Flash的特点是占用管脚比较少，作为系统的数据存贮非常适合，一般都是采用串行外设接口（SPI总线接口）。Flash存贮器与EEPROM根本不同的特征就是EEPROM可以按字节进行数据的改写，而Flash只能先擦除一个区间，然后改写其内容。一般情况下，这个擦除区间叫做扇区（Sector），也有部分厂家引入了页面（Page）的概念。选择Flash产品时，最小擦除区间是比较重要的指标。在写入Flash时，如果写入的数据不能正好是一个最小擦除区间的尺寸，就需要把整个区间的数据全部保存另外一个存贮空间，擦除这个空间，然后才能重新对这个区间改写。大多数Flash工艺更容易实现较大的擦除区间，因此较小的擦除区间的Flash的价格一般会稍贵一些。此外， SPI是标准的4线同步串行双向总线，提供控制器和外设之间的串行通信数据链路，广泛应用于嵌入式设备中。
Xilinx公司的新款FPGA都支持SPI接口。SPI总线通过4根信号线来完成主、从之间的通信，典型的SPI系统中常包含一个主设备以及至少一个从设备，在FPGA应用场合中，FPGA芯片为主设备，SPI串行FLASH为从设备。4个SPI接口信号的名称和功能如表5-8所示。
表5-8 SPI接口信号列表
一个主芯片和一个从芯片的通信接口如图M所示。FPGA通过SCLK控制双方通信的时序，在SS_n为低时，FPGA通过MOSI信号线将数据传送到FLASH，在同一个时钟周期中，FLASH通过SOMI将数据传输到FPGA芯片。无论主、从设备，数据都是在时钟电平跳转时输出，并在下一个相反的电平跳转沿，送入另外一个芯片。
图5-17 SPI接口连接示意图
其中SCLK信号支持不同的速率，一般常采用20MHz。通过SPI接口中的CPOL和CPHA这两个比特定义了4种通信时序。其中，CPOL信号定义了SCLK的空闲状态，当CPOL为低时，SCLK的低电平为空闲状态，否则其空闲状态为高电平；CPHA
定义了数据有效的上升沿位置，当其为低时，数据在第1个电平调转沿有效，否则数据在第2个电平跳转沿有效。其相应的时序逻辑如图M所示。
图5-18a CPHA为高时SPI的总线时序示意图
图5-18b CPHA为高时SPI的总线时序示意图
可以通过增加片选信号SS_n的位宽来支持多个从设备，SS_n的位宽等于从设备的个数。对于某时刻被选中的从设备和主设备而言，其读写时序逻辑和图M一样。
图5-19 多个从芯片的连接电路图
SPI串行FLASH作为一种新兴的高性能非易失性存储器，其有效读写次数高达百万次，不仅引脚数量少、封装小、容量大，可以节约电路板空间，还能够降低功耗和噪声。从功能上看，可以用于代码存储以及大容量的数据和语音存储，对于以读为主，仅有少量擦写和写入时间的应用来说，支持分区（多页）擦除和页写入的串行存储是最佳方案。
2．SPI串行FLASH配置电路
SPI串行配置模式常用于已采用了SPI串行FLASH PROM的系统，在上电时将配置数据加载到FPGA中，这一过程只需向SPI串行发送一个4字节的指令，其后
串行FLASH中的数据就像PROM配置方式一样连续加载到FPGA中。一旦配置完成，SPI中的额外存储空间还能用于其它应用目的。
1）SPI配置电路
虽然SPI接口是标准的4线接口，但不同的SPI FLASH PROM芯片采用了不同的指令协议。FPGA芯片通过变量选择信号VS[2:0]来定义FPGA和SPI FLASH的通信方式、FPGA的读指令以及在有效接收数据前插入的冗余比特数。常用SPI FLASH 与FPGA的有效操作配置如表M所示，其余的VS[2:0]配置留有它用。
表5-9 Xilinx芯片所支持的SPI FLASH存储器以及配置列表
从整体上看来，控制SPI串行闪存比较容易，只需要使用简单的指令就能完成读取、擦除、编程、写使能/禁止以及其它功能。所有的指令都是通过4个SPI引脚串行移位输入的。
不同型号的FPGA芯片具有数目不同的从设备片选信号，因此所挂的串行芯片数目也就不一样。例如：Spartan-3E系列FPGA芯片只有1位SPI从设备片选信号，因此只能外挂一片SPI串行FLASH芯片。在SPI串行FLASH配置模式下，
M[2:0]=3’b001。FPGA上电后，通过外部SPI串行FLASH PROM完成配置，配置时钟信号由FPGA芯片提供时钟信号，支持两类业界常用的FLASH。
图5-20给出了Spartan3E系列FPGA支持0X0B快速读写指令的STMicro 25系列PROM的典型配置电路。其中的Flash芯片需要Flash编程器来加载配置数据；单片的FPGA芯片构成了完整的JTAG链，仅用来测试芯片状态，以及支持JTAG 在线调试模式，与SPI配置模式没有关系。
图5-20 支持快读写得串行FLASH配置电路示意图
从中可以看出，SPI Flash容量大，适合于大规模设计场合。但由于SPI配置需要专门的Flash编程器，且操作起来比较麻烦，不适合在产品研发阶段调试FPGA 芯片，因此一般还会添加JTAG链专门用于在线调试。JTAG在线调试模式的原理以及注意事项将在5.3.5节进行详细说明。
图5-21给出了Spartan3E系列FPGA支持SPI协议的Atmel公司“C”、“D”系列串行Flash芯片的典型配置电路。这两个系列的FLASH芯片可以工作在很低温度，具有短的时钟建立时间。同样，单片的FPGA芯片构成了完整的JTAG链，仅用来测试芯片状态，以及支持JTAG在线调试模式，与SPI配置模式没有关系。
图5-21 Atmel SPI串行FLASH配置电路示意图
表5-20给出了SPI配置接口的连线的说明，每个SPI Flash PROM采用的名字略有不同，SPI Flash PROM的写保护信号和保持控制信号在FPGA配置阶段是不用的。其中HOLD管脚在配置阶段必须为高，为了编程Flash存储器，写保护信号必须为高。
2）相关信号说明
（1）FPGA端信号说明
对SPI配置模式下的FPGA信号进行说明，如表5-10所列。由于JTAG管脚已在多处提及，这里就不再介绍。
表5-10 配置电路中的FPGA管脚信号说明
（2）从设备Flash的管脚信号
由于不同公司不同型号的Flash管脚并不一致，下所以表5-11列出所有出现在串行Flash芯片上的信号，对于某一特定的Flash管脚，需要挑选其中的有效管脚，见表中的3-6列。
表5-11 配置电路中的SPI串行FLASH管脚信号说明
5.3.3 从串配置模式
从串配置模式的特点已在前文介绍，所用管脚的说明和主串模式一样，因此本节直接介绍从串配置电路原理以及注意事项。
在串行模式下，需要微处理器或微控制器等外部主机通过同步串行接口将配置数据串行写入FPGA芯片，其模式选择信号M[2:0]=3’b111，其典型的Spartan 3E 系列FPGA单片配置电路如图M所示。DIN输入管脚的串行配置数据需要在外部时钟CCLK信号前有足够的建立时间。其中单片FPGA芯片构成了完整的JTAG链，仅用来测试芯片状态，以及支持JTAG在线调试模式，与从串配置模式没有关系。外部主机通过下拉PROG_B启动配置并检测INIT_B电平，当INIT_B为高时，表明FPGA做好准备，开始接收数据。此时，主机开始提供数据和时钟信号直到FPGA 配置完毕且DONE管脚为高，或者INIT_B变低表明发生配置错误才停止。整个过程需要比配置文件大小更多的时钟周期，这是由于部分时钟用于时序建立，特别当FPGA被配置为等待DCM锁存其时钟输入。
图5-22 FPGA从串配置电路示意图
此外，从串配置模式也可配置多片FPGA芯片，典型的两片Spartan 3E系列FPGA 的从串配置电路如图M所示。所有芯片的CCLK信号都有主控设备提供，靠近主
控设备的FPGA要充当桥梁的作用，将配置数据转发到第二个FPGA芯片。可以看到采用从串配置的好处主要在于节省电路板面积，并使得系统具备更大的灵活性。
图5-23 多片FPGA从串模式配置电路
5.3.4 字节宽度外部接口并行配置模式
本节主要介绍基于闪存的FPGA配置方案，然后介绍字节宽度并行配置模式的配置电路，再对其配置信号进行说明，最后介绍其多片FPGA的配置电路。
1．并行Flash介绍
NOR和NAND是现在市场上两种主要的非易失闪存技术。NOR的特点是芯片内执行(Execute In Place，XIP)，这样应用程序可以直接在flash闪存内运行，不必再把代码读到系统RAM中。NOR的传输效率很高，在1～4MB的小容量时具有很高的成本效益，但是很低的写入和擦除速度大大影响了它的性能。NAND结构能提供极高的单元密度，可以达到高存储密度，并且写入和擦除的速度也很快,是高数据存储密度的理想解决方案。应用NAND的困难在于flash的管理和需要特殊的系统接口。
2．BPI单芯片配置模式
BPI配置电路
BPI配置接口主要用于支持标准的并行NOR闪存以及字节位宽或字位宽的PROM 芯片。在BPI模式下，FPGA从外部标准的NOR闪存或NAND闪存中，以字节宽度并行地获取配置数据，如Spartan 3E系列FPGA芯片在BPI模式下的NOR Flash
电路图M所示。当然，可以将该配置模式推广到其余并行配置外设中，地址、数据、片选（OE）以及写使能（WE）等控制信号都是通用的。
图5-24 BPI配置模式电路图
配置接口时序由FPGA芯片控制，最常用的方法是由CCLK管脚输出控制时钟，但是在单片BPI模式下并不使用CCLK信号，通过LDC[2:0]和HDC管脚来作为闪存的控制输入。
根据访问Flash地址的递增和递减，可以将BPI模式分为BPI UP模式和BPI DOWN 模式，由M[0]管脚决定，其控制如表M所列。但无论哪种模式，地址总是在CCLK 的下降沿变化。BPI UP和BPI DOWN模式增加了BPI的灵活性，使其能够和其余嵌入式处理器或CPU等共享闪存。如果其余设备从Flash底部启动（Boot），FPGA 可采用BPI UP模式，否则可采用BPI DOWN模式共享存储器。
表5-12 BPI地址控制模式简要说明
不同系列芯片对BPI模式的支持是不一样的，要在设计中特别小心。如表M列出了Spartan 3、Spartan-3E以及Spartan-3A系列FPGA芯片的BPI模式的支持的差异性。
表5-13 Spartan 3代芯片对BPI模式支持的差异列表
配置信号说明
并不是所有Xilinx所有FPGA都支持BPI配置模式，这里仍以Spartan 3E和Spartan 3A系列为例进行说明，各相关管脚的简要功能说明如表M所列（由于前文已提及JTAG管脚说明，这里不再介绍）。
表5-14 BPI模式下FPGA配置管脚说明列表
?电压适配性
大多数并行Flash都采用3.3V单电源供电，而BPI配置模式所需的管脚一般至
少分布在两个组（Bank）内，相应的FPGA分组必须使用3.3V电压来匹配并行Flash。同样，也有部分1.8V的并行Flash，因此相应的分组电平就必须采用1.8V。因此，设计之前要确定FPGA是否支持相应的电平，例如：由于Spartan-3A系列FPGA的上电复位（POR）电压就不支持1.8V，因此Spartan-3A不能外接并行Flash。
?BPI配置管脚的复用
当FPGA配置完成后，所有连接到闪存上的管脚都可以作为普通用户I/O。如果配置完后，不再使用闪存，可以将LDC0信号拉高，使其片选信号无效。其余管脚，包括A[25:0]或A[23:0]地址线、D[7:0]8根数据线、LDC2、LDC1以及HDC 等控制管脚。由于所有的管脚在配置后都是用户I/O，因此可以继续访问闪存。常见的闪存的容量为1~8M比特，甚至更大，而一片Spartan-3E系列FPGA芯片最多只需6M比特，因此可以用闪存剩余空间来存储应用程序的数据，如MicroBlaze软核的应用数据以及以太网设备的IP、MAC地址等。
例如：在嵌入式应用中，将FPGA逻辑电路和软核控制器MicroBlaze的应用数据所形成的比特文件存在闪存中，FPGA首先从闪存中读取逻辑的配置文件；等逻辑配置完毕后，再利用FPGA内部已形成的逻辑加载软核的应用数据，即可直接读取执行，也可以先将应用数据影射到DDR SDRAM，再从DDR SDRAM中读取程序并执行。当然，也可以将FPGA程序中所需要的大量非易失性应用数据存放在闪存中。
需要注意的是：不要将FPGA配置数据和用户数据存放在闪存的同一段中。
字节和字配置模式：
目前市场上的中小规模密度的闪存，容量一般在8M比特以下，只能作为比特宽度（8比特）的存储器来使用。大多数高密度的闪存芯片，容量一般都在16M比特以上，具有模式选择输入信号BYTE，可以支持字节宽度和字宽度（16比特）这两种读写方式。在图M中，FPGA芯片的LDC2管脚用来选择配置位宽模式，支持字模式读写。字节宽度和字宽度模式的电路连接是不同的。
虽然Spartan-3E系列FPGA支持字节/字模式且连接简单，但需要注意的是：不同厂家的闪存芯片地址线的管脚数和命名规则是不一样的，在连接时要确保FPGA和闪存连接正确。如Intel、Micron等公司采用简意思路，管脚多较多，其名称和FPGA一致，比较直观（如A0，D15等），但闪存的A0脚在字模式中是不用的，且需要一个额外的用户I/O连接到D15脚，如图M所示。
另外的一类生产商，如AMD、Atmel等公司，采用高效的思路，管脚数较少，且通过管脚IO15/A-1来实现两种模式的选择，在配置时选用字节宽度，配置后应用程序使用字宽度读取数据，如图M所示。在字节宽度中，BYTE#=0，由FPGA
芯片的LDC2控制。IO15/A-1信号控制选择字节定位，地址线A0用于选择字定位。当FPGA配置成功后，应用程序驱动BYTE#=1，选择16比特的字模式读取时钟，确保D[14:8]连接到用户I/O管脚上，D15连接到FPGA的A0管脚。其中
IO15/A-1是最重要的数据比特，如果一款闪存芯片有IO15/A-1管脚或DQ15/A-1，在连接时一定要根据图M来连接。
实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 四、程序流程图、算法及运行结果 3-1 #include
return -1; } int main() { char s[MAXSIZE]; char t[MAXSIZE]; int answer, i; printf("S String -->\n "); gets(s); printf("T String -->\n "); gets(t); printf("%d",StrIndex_BF(s,t)); /*验证*/ if((answer=StrIndex_BF(s,t))>=0) { printf("\n"); printf("%s\n", s); for (i = 0; i < answer; i++) printf(" "); printf("%s", t); printf("\n\nPattern Found at location:%d\n", answer); } else printf("\nPattern NOT FOUND.\n"); getch(); return 0; }
模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。
在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx”
《数据结构》课程设计报告 题目：模式匹配算法KMP及其应 用 学院 （系）： 班级： 学生学 号： 姓名： 指导教 师： 日期： 目录
摘要 (1) 一、绪论 (2) 1. 课程设计的背景 (2) 2. 课程设计的意义 (3) 3. 开发平台及其简介 (3) 二、需求分析 (3) 三、可行性分析 (5) 四、概要设计 1. 功能设计要求 (5) 2. 总体结构设计 (6) 3. 抽象数据类型串的定义 (9) 4. 函数调用关系 (10) 5. 主程序调用 (11) 五、详细设计 (12) 1. 宏定义 (12) 2. 数据元素结构定义 (13)
3. 功能具体实现 (13) 4. 主程序和菜单设计 (29) 六、设计和调试分析 (31) 七、测试结果 (33) 八、设计心得体会 (37) 九、用户手册 (37) 一十、附录 (43) 一十一、参考文献 (44) 摘要 本程序主要是通过获取一个子串，或新建一个新的文本文件，或和已有的文本文件进行匹配，分别利用了串的朴素模式匹配算法、串的模式匹配KMP算法、串的模式匹配改进算法等数据结构中学的知识实现了，在和文本文件中的主串进行匹配后返回子串在文本文件中出现的次数和出现位置所在的行的行号。 本程序除了实现串在定长顺序存储结构下的三种模式匹配算法，还实现了串在单链表存储结构下的模式匹配KMP算法，通过比较了串的不同存储结构下串的模式匹配算法，进一步加强了对串的理解及串的各类模式算法的掌握。 在使用串的定长存储结构时，考虑到书本上实现串的KMP算法时，储存串的数组下标是从1开始，为了进一步理解串，本程序另辟蹊径，特地定义了一个结构体，结构体中用来存储串的数组下标是从0开始，实现了串的模式匹配KMP算法。
第四章串 教学目的与要求 本章目的是介绍串的逻辑结构、存储结构及其串上的基本运算。 重点和难点 本章重点是掌握串上实现的模式匹配算法，其也是本章难点。 教学内容 第一节串的基本概念 ４.1.1 基本概念 串：是零个或多个字符组成的有限序列。串中所包含的字符个数称为串的长度。 空串：长度为0的串称为空串，它不包含任何字符。 空白串：仅由一个或多个空格组成的串称为空白串。应注意空串和空白串的区别。 子串、主串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。空串是任意串的子串，任意串是其自身的子串。 子串在主串中的位置：通常，将子串在主串中首次出现时子串首字符对应的主串中的序号定义为子串在主串中的位置。 ２．串的基本运算 （１）求串的长度（Length） （２）串复制 (Copy)： （３）串联接 (Concat)
（４）串比较 (Compare) （５）字符定位(Index) 除上述基本运算外，串运算还有求子串、子串的定位、子串的置换等操作。这些操作，一般可由这些基本操作实现。 第二节串的存储结构 4.2.1串的顺序存储 1.静态存储分配的顺序串 顺序串最简单的描述形式是直接使用定长的字符数组来定义。其定义形式为 # define maxstrsize 256 typedef char Seqstring[maxstrsise]; 利用类型描述符Seqstrsring可定义数组变量存储串，利用特定字符表示串的结束(Ｃ语言用转义字符’\0’) 。例如Seqstrstring s; 变量s可存储长度不超过255个字符的字符串，以’\0’作为串的结束。 顺序串的类型定义也可以象线性表的顺序存储一样，在定义字符数组的基础上，引入描述长度的成员。其定义形式为 # define maxstrsize 256 typedef struct { char ch[maxstrsise]; int length; }Sqestring;
第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2, ‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】 A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长 4．已知串S=‘aaab’,其Next数组值为（）。 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．012345678999 B．012121111212 C．011234223456 D．0123012322345 6．字符串‘ababaabab’的nextval 为（） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。 A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下：
/*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1； } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m).
实验内容与要求 内容： 问题描述：从键盘输入一个目标串S，并输入要匹配的模式串T，利用串的简单的模式匹配和KMP算法，定位模式串在主串中的位置。 要求： 设计要求 首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 主控菜单设计要求：程序运行后，显示一个标题“模式匹配算法”，标题下方给出6个菜单项的内容和输入提示： 1．输入一个主串S 2．输入一个模式串T 3. 计算模式串T的next函数值 4．实现简单模式匹配 5．实现KMP模式匹配 6. 继续/否？（y/n?） #include j=next[j]; } } void printNext(String T) { int i; for(i=1;i<=T[0];i++) { printf("next[%d]:%d ",i,next[i]); } printf("\n"); } int KMP_INDEX(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0] &&j<=T[0]) { if(j==0||S[i]==T[j]) { i++; j++; } else j=next[j]; } if(j>T[0]) return i-T[0]; else return 0; } int Index(String S,String T,int pos) { int i=pos,j=1; while(i<=S[0] &&j<=T[0]) { 小叶紫檀手串打结图解教学 小叶紫檀手串打结图解教学？喜欢紫檀手串的玩友有没研究过小叶紫檀手串打结图解教学的问题呢？ 如今，佛珠手串逐渐受到更多人的喜爱，文玩爱好、时尚人士以及仅仅是作为手串配饰的人们都会有人去挑选一串适合自己的佛珠手串。因为佛珠手串比起平常的手串饰品多了一份含义，一份庄重，一种信仰亦或是一种真诚的内心愿望。 那么小叶紫檀手串怎么打结？方法其实有很多，例如金刚结、四股辫、十字结、8字结、吉祥结和团锦结等等。小编之前介绍过8字结、吉祥结的寓意和编法。今天就主要来讲小叶紫檀手串打结图解教学之团锦结 团锦结的形状特点是圆满美丽，变化多端，其耳翼成花瓣状，类似花形，结体虽小但漂亮且不易松散，可镶嵌珠石以作装饰。在我国传统文化中，“圆”是吉祥和谐的代表，如“团圆”。所以团锦结那如圆月又如锦花般的形状，贴切的表达着团圆美满，锦上添花，花团锦簇，前程似锦的美好寓意。非常适合手持的打结或打算用于悬挂墙上的小叶紫檀手串打结方法。 讲十字结和团锦结的寓意和编法吧! 小叶紫檀手串打结图解教学之十字结 “十”含有满足的意思，如“十分”“十足”。本结编制完成后，其正面为“十”字，故称“十字结”，其背面为方形，故又称方结、四方结。同时，也有称之为成功结或皇冠结的。 十字结在结饰的组合中，由于其结形简单、编制讯速，可当做装饰结使用。 越来越多的人喜欢佩戴佛珠手串，而各种材质的佛珠也特别的多，各式各样，还增加了一些时尚的元素。因此，萝卜白菜各有所爱，人们总是会去寻找那些与自己有缘分的佛珠手串。据统计，我国每年网购加上实体店购买手串类的交易额达几十个亿之多，但基本上十檀九假，除了像儿孙福这样的大品牌，基本上普通买家很难能买到正品。所以想入手紫檀手串却还未入手的玩友们，要谨防吃药上当哦。 佛珠手串的佩戴不分男女，不管你是否信仰佛教，只要你喜欢戴手串，都能佩戴。佛珠对于当下的人们来说，它总是比平常的手串饰品多了些庄重，一层含义，更是一种信仰也是人们对于内心美好愿望的一种寄托。 怎么样？结合图解是不是觉得十字结和团锦结这两种打结方法，还是很容易学会的呢。如果你用的是一颗向善的心，无论怎么样打佛珠结都是最好的。当然学学还是有必要的！以免以后不小心佛珠手串的绳子松了，束手无策哦。 Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 小叶紫檀手串打结图解 小叶紫檀手串打结怎么做？瞎搞八搞结果打出来的结丑出天际？没关系，小编为你整理了一些小叶紫檀手串打结图解，根据以下的小叶紫檀手串打结图解，自己在家也能轻松简单的打出美美的结啦！ 如今，佛珠手串逐渐受到更多人的喜爱，文玩爱好、时尚人士以及仅仅是作为手串配饰的人们都会有人去挑选一串适合自己的佛珠手串。因为佛珠手串比起平常的手串饰品多了一份含义，一份庄重，一种信仰亦或是一种真诚的内心愿望。那么小叶紫檀手串怎么打结？方法其实有很多，例如金刚结、四股辫、十字结、8字结、吉祥结和团锦结等等。小编之前介绍过8字结、吉祥结的寓意和编法。今天就主要来讲讲十字结和团锦结的寓意和编法吧! 小叶紫檀手串打结图解之十字结 “十”含有满足的意思，如“十分”“十足”。本结编制完成后，其正面为“十”字，故称“十字结”，其背面为方形，故又称方结、四方结。同时，也有称之为成功结或皇冠结的。 十字结在结饰的组合中，由于其结形简单、编制讯速，可当做装饰结使用。 小叶紫檀手串打结图解之团锦结 团锦结的形状特点是圆满美丽，变化多端，其耳翼成花瓣状，类似花形，结体虽小但漂亮且不易松散，可镶嵌珠石以作装饰。在我国传统文化中，“圆”是吉祥和谐的代表，如“团圆”。所以团锦结那如圆月又如锦花般的形状，贴切的表达着团圆美满，锦上添花，花团锦簇，前程似锦的美好寓意。非常适合手持的打结或打算用于悬挂墙上的小叶紫檀手串打结方法。 小叶紫檀手串真假问题 好的结当然是要配好的手串，但是好的手串却难挑，有时候其实咱们技术到位了，依旧难以选择出好的符合自己心意的手串。是我们自己眼光太高？其实不然，而是因为市场上“伪装者”太多！有时候往往会出现这种有趣的现象：真货无人问津，假货前倒是门庭若市，据统计，我国每年网购加上实体店购买手串类的交易额达几十个亿之多，但基本上十檀九假，除了以儿孙福小叶紫檀为首的三大名檀，基本上普通买家很难能买到正品。无奈啊真是的无奈！ 绳子打结方法大全图解 半结 简 介:所有绳结的基本结。 用 途:防止滑动、或是在绳子未端绽开时可做为暂时防止继续脱线。缺点:当结打太 紧或弄湿时很难解开。 八字结 简介:打法简单、易记。 用途:可作为一条绳上的一个临时或简单中止，制动点。 特征:即使两端拉得很紧，依然可以轻松解开。 平结 用途:将同一条绳的两端绑在一起。适用于连结同样粗细、同样质材的绳索；但不适用在较粗、表面光滑的绳索上。 特征:缠绕方 法一旦发生错误，结果可能会变成个不完全的活结，用力一拉结目就会散开。其结目如果拉得太紧，就不太容易解开；不过如果双手握住绳头，朝两边用力一拉，就 可轻松解开。 秘诀:左搭右、右搭左。 双套结 简介:其它绳结的开头和结束之用。 用途:通常应用在两端施力均等的物品上，适用于水平拉力之下。 特征:具备极 高的安全性，不过，如果只在绳索的一端使力的话，双套结的结目可能会乱掉或松开。 三套结 简介:作用和双套结相同，但较为牢固。 用途:应用在垂直方向的拖力。 其它:又称为转动结( Rolling Hitch)，马格纳斯结 ( Magnus Hitch ) ，拉绳结 ( Taut-line Hitch)，止索结 ( Stopper Hitch ) 。 渔人结 简介:此结十分容易打，但很难拆开。故应尽量避免用在一些质地好的绳上，也不好用在会扯得很紧的绳上，因扯紧后，很难解开。 用途:将两条绳绳连接一起，通常是硬和软的两条绳。 普鲁士结 营 钉结 简介:可让你将结位在绳上随时上下移动。 用途:用在各种斜拉绳的收尾。 特征:可随时调较绳的松紧度。 缩绳结 用途:将长绳收短，以免要因太长而要剪短，也可用此法加强绳上容易磨损部份的保护。特征:如绳太松，则此结很容易松散而失去作用。 接绳结 用途:将两条绳按在一起。 特征:容易解开。 拉 柴结/系 木结 简介:拥有一个可随意调整的圈。 用途:绑紧及拖拉木材之类的物品。 实验四顺序串的各种模式匹配 一、实验目的 熟悉串的有关概念，掌握串的存储结构及串的模式匹配算法。 二、实验内容 由用户随意输入两个串：主串S和模式串T，设S=‘s1s2…sn’，T=‘t1t2…tm’，且0 s->next=p->next; p->next=s; } void main(){ int num,e,x,y,count=-1,c=0,e1,t=-2147483648; bool mark=false; lin* L,* tx,* p,* q; L=(lin*)malloc(sizeof(lin)); L->next=NULL; cout<<"输入个数>=2"< 第四章串 一、内容提要 1、是数据元素为字符的线性表，串的定义及操作。 2、串的基本操作，编制算法求串的其它操作。 3、串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。静态和动态（块链结构，堆结构）存储的优缺点。 4、朴素模式匹配算法及改进（KMP）算法。 二、学习重点 1、串的基本操作，编写串的其他操作（如index,replace等）。 2、在串的模式匹配中，求匹配串的nextval 函数值。 3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。 5、串操作在存储结构下的实现。 三、例题解析 1、利用串的如下基本运算 create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法 replace(string &s,string t, string v) //本算法实现串的置换操作，用串v置换串s中所有非重叠的t串。 {i=INDEX(s,t);{判s中有无t} IF (i!=0) {CREATE (temp, ‘’);{t为临时串变量，存放部分结果} m=LENGTH(t);n=LENGTH(s); WHILE (i!=0) { ASSIGN (temp,CONCAT(temp,SUBSTR(s,1,i-1),v)); //用v替换t形成部分结果 ASSIGN (s,SUBSTR(s, i+m,n-i-m+1)); //t串以后形成新s串 n= n-(i-1)-m; i=INDEX(s,t); } ASSIGN (s,CONCAT(temp,s)); //将剩余s连接临时串t再赋给s } } int index(string s,string t) //本算法求串t在串s中的第一次出现。结果是：若t在s中，则给出串t的第一个字符在串s中的位置，若不存在，则返回0 {j=1;m=length(s); n=length(t); eq=true; WHILE((j<=m-n+1)&& eq ) IF equal(substr(s,j,n),t) eq=false; ELSEj=j+1； IF( j<=m+n-1)return(j); Return(0); //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; } 绳子打结方法大全图解 SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN# 绳子打结方法大全图解 半结 简 介:所有绳结的基本结。 用 途:防止滑动、或是在绳子未端绽开时可做为暂时防止继续脱线。 缺点:当结打太 紧或弄湿时很难解开。? 八字结 简介:打法简单、易记。 用途:可作为一条绳上的一个临时或简单中止，制动点。 特征:即使两端拉得很紧，依然可以轻松解开。 平结 用途:将同一条绳的两端绑在一起。适用于连结同样粗细、同样质材的绳索；但不适用在较粗、表面光滑的绳索上。 特征:缠绕方 法一旦发生错误，结果可能会变成个不完全的活结，用力一拉结目就会散开。其结目如果拉得太紧，就不太容易解开；不过如果双手握住绳头，朝两边用力一拉，就 可轻松解开。 秘诀:左搭右、右搭左。? 双套结 简介:其它绳结的开头和结束之用。 用途:通常应用在两端施力均等的物品上，适用于水平拉力之下。 特征:具备极 高的安全性，不过，如果只在绳索的一端使力的话，双套结的结目可能会乱掉或松开。? 三套结 简介:作用和双套结相同，但较为牢固。 用途:应用在垂直方向的拖力。 其它:又称为转动结( Rolling Hitch)，马格纳斯结 ( Magnus Hitch ) ，拉绳结 ( Taut-line Hitch)，止索结 ( Stopper Hitch ) 。? 渔人结 简介:此结十分容易打，但很难拆开。故应尽量避免用在一些质地好的绳上，也不好用在会扯得很紧的绳上，因扯紧后，很难解开。 用途:将两条绳绳连接一起，通常是硬和软的两条绳。? 普鲁士结? 营 钉结 简介:可让你将结位在绳上随时上下移动。 用途:用在各种斜拉绳的收尾。 特征:可随时调较绳的松紧度。? 缩绳结 用途:将长绳收短，以免要因太长而要剪短，也可用此法加强绳上容易磨损部份的保护。 第四章串习题及答案 一、基础知识题 4.1简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 4.2假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么? (4)调用函数strcmp(&s1[5],"ton")的返回值是什么? (5)调用函数stlen(strcat(s1,s2))的返回值是什么? 4.3设T[0..n-1]="adaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T 时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 二、算法设计题： 4.4利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。 4.5利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 4.6以HString为存储表示，写一个求子串的算法。 4.7一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。 4.8写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。 注意： S和P的长度不一定相等。可以使用已有的串操作。 4.9将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。 *4.10利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。 4.11若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 答案： 4.1简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 串的匹配算法——Brute Force (BF)算法 匹配模式的定义 设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。通常把主串S称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串S中找到一个模式串T；不成功则指目标串S中不存在模式串T。 BF算法 Brute-Force算法简称为BF算法，其基本思路是：从目标串S的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串S的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串S中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0. /*T非空。 int index(String S, String T ,int pos) { int i=pos; //用于主串S中当前位置下标，若pos不为1则从pos位置开始匹配int j =1; //j用于子串T中当前位置下标值 while(i<=S[0]&&j<=T[0]) //若i小于S长度且j小于T的长度时循环 { if(S[i]==T[j]) //两个字母相等则继续 { ++i； ++j； } else //指针后退重新开始匹配 { i=i-j+2; //i退回到上次匹配首位的下一位 j=1； } if(j>T[0]) return i-T[0]; else return 0; } } BF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m 次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m 从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是O(n+m). 数据结构面试之十四——字符串的模式匹配 题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。 十四、字符串的模式匹配 1. 模式匹配定义——子串的定位操作称为串的模式匹配。 2. 普通字符串匹配BF算法（Brute Force 算法，即蛮力算法） 【算法思想】： 第（1）步；从主串S的第pos个字符和模式的第一个字符进行比较之，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较之。 第（2）步骤；依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功；函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称为匹配不成功，函数值为0。 比如对于主串S=”abacababc”; 模式串T=”abab”; 匹配成功，返回4。 对于主串S=”abcabcabaac”; 模式串T=”abab”; 匹配不成功，返回0。 【算法实现】： //普通字符串匹配算法的实现 int Index(char* strS, char* strT, int pos) { //返回strT在strS中第pos个字符后出现的位置。 int i = pos; int j = 0; int k = 0; int lens = strlen(strS); int lent = strlen(strT); while(i < lens && j < lent) { if(strS[i+k] == strT[j]) { ++j; //模式串跳步 ++k; //主串(内)跳步 } else { i = i+1; j=0; //指针回溯，下一个首位字符 k=0; } }//end i if(j >= lent) { return i; } else { return 0; } }//end [算法时间复杂度]：设主串长度为m,模式串的长度为n。一般情况下n 不花钱不求人!史上最全手串打结方法详解! 对于很多玩友来说，手串打各种各样的结看起来是非常有难度的，往往需要花钱找人帮忙操作。其实掌握了下面的方法技巧，完全可以自己完成，不花钱不求人!关于绳子的选择就不啰嗦了，根据自己手串珠子的大小进行选择即可，这就来看看下面的介绍吧。第一种，吉祥结。吉祥结是最为常见的，多数出现在木质手串佛头的下面，代表吉祥的蕴意，方法不复杂，一学就会。 用一条绳子整理出三只耳朵的形状。 下面的两条线向上折叠，压住最右边的哪个耳朵，需要留有一定的空隙。 逆时针操作，重复上一步的步骤。 将最左侧的耳朵穿入到下方两条线留有的空隙中。 收紧，就可以看到简单的形状了。 想要让吉祥结看起来更加的饱满，还需要按照1-5的步骤重 新的编织一遍。 继续整理就是完整的吉祥结了。 第二种，金刚结。金刚结的用途多数是用于佛头下面珠子之间的间隔，为了方便使用，尽量选择有弹力的线，不然边上之后就不能动了。 掌握图中佛塔黑线和红线的走向是非常关键的，必须要拿捏好位置，这样才不会走形。 按照逆时针的方向打圈。 按照图中所示的方向进行穿绳拉紧。 第三种，凤尾结。凤尾结主要是用于手串最下面的弟子珠首尾的部分，起到的是美化整体的作用。多数在星月菩提手串中使用。凤尾结也被称为是发财结，象征龙凤呈祥的寓意，即便是不用子弟珠，直接使用凤尾结代替也是不错的。 第四种，平结。平结主要是用于非弹力线的活动部分，在编织好之后，是可以上下进行移动的。 平结其实是比较常用，也是最容易掌握的一种。只需要根据图片中的方法一步步操作就可以了，没有太高的技术含量，一学就会。 看到这里，相信玩友们对于常用的手串打结方法已经了解了。在穿绳的时候，若是使用到的是线绳，那么就避免不了需要使用打火机来烧绳子，在用手拉的时候会感觉非常的烫。有一个比较简单可行的方法，在烧之前，可以在自己的手上沾上一些凉水，这样可以起到缓冲效果，不会烫手。掌握了这么多的方法，这就来自己尝试一下吧。小叶紫檀手串打结图解教学
字符串匹配算法总结
小叶紫檀手串打结图解
绳子打结方法大全(图解)
串的模式匹配
第四章 串
串的朴素模式匹配算法(BF算法)
绳子打结方法大全图解
第四章 串 习题及答案
串的模式匹配算法
C语言字符串模式匹配
不花钱不求人!史上最全手串打结方法详解!
相关主题
文本预览