字符串匹配KMP算法，从目标串的右边对模式串进行匹配，输出模式串的位置。

水深无声 2023-01-01 03:36 107阅读 0赞

### ** KMP算法，从目标串的右边对模式串进行匹配，输出模式串的位置。** ###

--------------------

#include "stdafx.h"
    #include<iostream>
    #include<string>
    #include <time.h>
    
    using namespace std;
    
    
    
    //从键盘输入你的学号和姓名，完成考试算法后在屏幕上输出你的姓名和学号，及完成时间。 
    //KMP算法，从目标串的右边对模式串进行匹配，输出模式串的位置。 
    
    
    typedef struct {
        char name[20];
        char Sno[50];
    }Message;
    
    Message My;         //存放我的信息
    
    void setMessage(){
        
        printf("输入你的学号:");
        gets(My.Sno);
        fflush(stdin);
        printf("输入你的姓名:");
        gets(My.name);
        fflush(stdin);
    }
    
    void getMessage(){
        
        printf("学号:%s\n",My.Sno);
        printf("姓名:%s\n",My.name);
    	time_t t;
    	struct tm *timeinfo;  
    	time(&t);
    	timeinfo = localtime(&t);
    	printf("程序结束时间：%s\n", asctime(timeinfo));  
    	printf("\n");
        system("pause");
    }
    
    
    
    //获取next数组
    void getNext(int next[], string T) {
    	int i = 0;//j为P串的下标，k用来记录该下标对应的next数组的值
    	int j = -1;
    	next[0] = -1;//初始化0下标下的next数组值为-1
    
    	while (i < T.length()) {//对模式串进行扫描
    		if (j == -1 || T[i] == T[j]) {//串后缀与前缀没有相等的子串或者此时i下标下的字符与j下的字符相等。
    				++i;
    				++j;
    				next[i] = j;//设置next数组i下标的值为j
    		}
    		else {
    			j = next[j];//缩小子串的范围继续比较
    		}
    	}
    }
    
    //kmp匹配
    int kmp(string T, string pat) {
    	int posP = 0, posT = 0;//posP和posT分别是模式串pat和目标串T的下标，先初始化它们的起始位置
    	int lengthT = T.length();
    	int lengthP = pat.length();
    	int *next = new int[lengthT];
    	getNext(next, T);//获取next数组
    	while (posP < lengthP&&posT < lengthT) {//对两串扫描
    		if (posP == -1 || pat[posP] == T[posT]) {//对应字符匹配
    			posP++;posT++;
    		}
    		else
    			posP = next[posP];//失配时，用next数组值选择下一次匹配的位置
    	}
    	if (posP < lengthP) return -1;
    	else return posT - lengthP;//匹配成功
    }
    
    //反转字符串
    string reverseString(string T) {
    	string temp;
    	for (int i = T.length()-1; i >=0 ; i--)
    	{
    		temp += T[i];
    	}
    	return temp;
    }
    
    int main() {
    	/*
    	主串： ABCAACBBCBADAABCACBD
    	匹配串 BD
    
    	从右边开始匹配的串
    	主串：DBCACBAADABCBBCAACBA
    	匹配串 DB
    	*/
    
    	setMessage();
    	string T, pat;
    	cout << "请输入主串" << endl;
    	cin >> T;
    	
    	cout << "请输入子串" << endl;
    	cin >> pat;
    	T = reverseString(T);
    	pat = reverseString(pat);
    	int lengthT = T.length();
    	int *next = new int[lengthT];
    	getNext(next, T);//获取next数组
    	int pos = kmp(T, pat);//pos用于存找到的数字的位置，是+1的，如有需要可-1
    	cout << "子串的位置在:" << pos << endl;
    	/*
    	cout << "nextP[]:[";
    	for (int i = 0;i < lengthT;i++) {
    		cout << next[i] << " ";
    	}
    	cout << "]" << endl;
    	*/
    	getMessage();
    
    	return 0;
    }