串的匹配模式算法

系统管理员 2022-05-15 13:47 185阅读 0赞

关于算法原理，网上有很多优秀的博客都有讲解，这里我就只记录一下自己用代码实现的过程

## BF算法（c）： ##

1.主串与模式串逐个字符进行比较，

2.出现字符不匹配时主串的比较位置重置为起始位置的下一个字符位置，模式串的比较位置重置为起始位置，

3.最终匹配成功返回主串中匹配模式串的起始位置，否则返回-1

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_SIZE 100
    
    /**数组长度包括 \0,字符串长度不包括 \0*/
    
    /**strlen求实际长度，sizeof求所占空间*/
    
    /** 定义结构体 */
    typedef struct String{
        char str[MAX_SIZE];
        int length;
    }String;
    
    /** 初始化函数 */
    void Init(String *Str,char str[]);
    /** BF算法实现 */
    int BF(String parentString,String patternString,int index);
    
    int main()
    {
        String parentString;
        String patternString;
        int index;
    
        Init(&parentString,"abcdefghijklmn");
        Init(&patternString,"ghijki");
    
        index = BF(parentString,patternString,5);
        printf("匹配结果：%d\n",index);
        return 0;
    }
    
    void Init(String *Str,char str[])
    {
        int i;
        if(strlen(str) > MAX_SIZE)
        {
            for(i = 0;i < MAX_SIZE; i++)
            {
                Str->str[i] = str[i];
            }
            Str->length =  strlen(str);
        }else{
             Str->length =  strlen(str);
             for(i = 0;i < Str->length; i++)
            {
                Str->str[i] = str[i];
            }
        }
    }
    
    int BF(String parentString,String patternString,int index)
    {
        int j = 0;//字串的起始下标，index为主串的起始下标
        while(index < parentString.length && j < patternString.length){
            if(parentString.str[index] == patternString.str[j])
            {
                //一个字符匹配成功就匹配后一个，直到整个子串都匹配完
                j ++;
                index ++;
            }else{
                //匹配失败，从第一个匹配成功的字符的后面一个字符重新开始匹配
                index = index - j + 1;
                j = 0;
            }
        }
        if(j == patternString.length)
            //匹配成功，总共匹配了patternString.length个元素，所以第一个匹配成功字符下标为index - j
            return index - patternString.length;
        else
            return -1;
    }

## KMP算法： ##

原理部分：[KMP原理][KMP]

**需移动的位数 = 已匹配字符位数 - 失配字符的上一位字符所对应的最大长度值**

**上一位字符所对应的最大长度值(用next\[ \]表示)：已匹配字符串的前缀和后缀的最长共有元素长度**

**比如abcac  前缀：a,ab,abc,abca**

**                   后缀：bcac,cac,ac,c**

**最大共有元素长度为0**

。。。为了next求到泪奔。。。暂时先放下了

## **SunDay算法（java）：** ##

public class TestSunDay {
    
    	public static void main(String[] args) {
    		
    		String source = "acfdedfacfdbea";
    		String target = "acfdbe";
    
    		int i = SunDay(source.toCharArray(),target.toCharArray(),0);
    		System.out.println("匹配结果：" + i);
    	}
    	
    	/**
    	 * 
    	 * @param tempS 主串
    	 * @param tempT 子串
    	 * @param indexS 遍历主串是从indexS下标处开始遍历
    	 * @return
    	 */
    	public static int SunDay(char[] tempS, char[] tempT,int indexS) {
    		if(indexS >= tempS.length)
    			return -1;
    		//遍历子串是从indexT下标处开始遍历
    		int indexT = 0;
    		//计数匹配了多少个字符
    		int count = 0;
    		for (int i = indexS; i < indexS + tempT.length; i++) {
    			if (tempS[i] == tempT[indexT]) {
    				indexT ++;
    				count ++;
    			} else {
    				break;
    			}
    		}
    		//匹配的字符数和子串的长度相等，即匹配成功
    		if (count == tempT.length) {
    			return indexS;
    		}	
    		//匹配失败，看后面一个字符在子串中有没有相同的
    		if(indexS + tempT.length < tempS.length){
    			int i = check(tempS[indexS + tempT.length],tempT);
    			if( i == -1){
    				//没有相同的就子串就后移子串长度个位置
    				indexS += tempT.length;
    				//再重新匹配
    				return SunDay(tempS, tempT, indexS);
    			}else{
    				//后面一个字符在子串中有相同的,子串往后移若干位，使得这两个字符对其
    				indexS = indexS + tempT.length - i;
    				return SunDay(tempS, tempT, indexS);
    			}
    		}else{
    			return -1;
    		}
    	}
    
    	
    	/**
    	 * 判断在tempT数组中有没有c这个字符
    	 * @param c
    	 * @param tempT 
    	 * @return 返回c在tempT中的下标，没有就返回-1
    	 */
    	public static int check(char c, char[] tempT) {
    		for (int i = 0; i < tempT.length; i++) {
    			if(c == tempT[i])
    				return i;
    		}
    		return -1;
    	}
    		
    }

**        **

[KMP]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html