輸入主串a，模式b
b在a中的位置
1.在串a和串b中設定比較的下標i=0，j=0；
2.重復下述操作，直到a或b的所有字符均比較完畢：
2.1如果a[i]等于b[i]，繼續比較a和b的下一對字符；
2.2負責，下標i和j分別回溯，開始下一趟匹配；
3.如果b中所有字符均比較完，則匹配成功，回傳本趟匹配的起始位置；負責匹配失敗，回傳0；
#include<iostream> #define N 100000 using namespace std; char a[N],b[N]; int BF(char a[],char b[])//BF演算法 { int i = 0,j = 0;//i，j變數分別表示在主串和模式串的位置 int start = 0;//start記錄主串回溯的位置 while(a[i] != '\0' && b[j] != '\0') { if(a[i] == b[j]) { i++; j++; } else { start++; i = start; j = 0; } } if(b[j] == '\0')//如果是模式串所有匹配完成，即匹配成功，回傳位置 return start + 1; else//否則匹配失敗 return 0; } int main() { int t; cin >> t;//t個測驗樣例 while(t--) { int flag;//模式匹配成功的位置 cin >> a >> b;//讀入字串 flag = BF(a,b); cout << flag << endl; } return 0; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/96301.html
標籤：C++
上一篇：數位的處理