字符串T = abcabaabaadac, 字符串P = abaa,判斷P是否是T的子串，就是字符串匹配問(wèn)題了，T叫做文本(Text),P叫做模式(Pattern).托福代考 職稱英語(yǔ)代考

　　算法思想

　　樸素的字符串匹配過(guò)程可以形象的看成一個(gè)包含模式的“模板”P沿文本T移動(dòng)，同時(shí)對(duì)每個(gè)位移注意模板上的字符是否與文本中的相應(yīng)字符相等。外層循環(huán)的次數(shù)最多為len(s) - len(p),內(nèi)層循環(huán)的次數(shù)最多為len(p).

　　最壞情況下的時(shí)間復(fù)雜度：O((len(T) - len(P) + 1) * len(P))

　　兩個(gè)for循環(huán)，代碼比較簡(jiǎn)單，但是效率很低

　　算法代碼

　　[cpp]

　　#include <stdio.h>

　　#include <stdlib.h>

　　#include <string.h>

　　void main()

　　{

　　char part[20], str[50];

　　int i, flag, j, len_p, len_s, k;

　　while(scanf("%s %s", part, str) != EOF)

　　{

　　//獲取字符串長(zhǎng)度

　　len_p = strlen(part);

　　len_s = strlen(str);

　　//樸素字符串匹配算法

　　for(i = 0, flag = 0; i < len_s - len_p + 1; i ++)

　　{

　　for(j = i, k = 0; part[k] == str[j] && part[k] != '\0' && str[k] != '\0'; j ++, k ++)

　　{

　　}

　　if(k > 0 && part[k] == '\0')

　　{

　　flag = 1;

　　break;

　　} http://

　　}

　　//輸出匹配成功or失敗

　　if(flag)

　　printf("匹配成功,匹配位置是:%d\n", i + 1);

　　else

　　printf("匹配失敗!\n");

　　}

　　}

　　算法記號(hào)與術(shù)語(yǔ)

　　用 Σ* 表示用字母表Σ中的所有有限長(zhǎng)度的字符串的集合

　　字符串x的長(zhǎng)度用|x|表示證券從業(yè)代考

　　x和y的連接表示為xy,長(zhǎng)度為|x| + |y|

　　x = yw, y是x的前綴，w是x的后綴