BK与KMP算法

#include

#define fi first
#define se second
#define PI acos(-1)
#define mk make_pair
#define lowbit(x) (x & (-x))
#define sz(x) (int)(x).size()
#define all(a) a.begin() , a.end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define pre(i, b, a) for (int i = (b); i >= (a); --i)
#define debug freopen("1.in", "r", stdin), freopen("1.out", "w", stdout);

using namespace std;

typedef long long LL;
typedef pair PII;
const int INF = 0x3f3f3f3f;
const int N = 1000010;

char s[N] , p[N];
int n , m;
int cnt1 , cnt2;
int ne[N] , neva[N];

void get_next(char str[])
{
    int i = 1 , j = 0;
    ne[1] = 0;
    while(i <= strlen(str + 1))
    {
        if (j == 0 || str[i] == str[j]) {
            ++ i , ++ j;
            ne[i] = j;
        }
        else j = ne[j];
    }
}

int kmp(int pos)
{ 
    int i = pos  , j = 1;
    while(i <= n && j <= m)
    {
        if (j == 0 || s[i] == p[j]) {
            ++ i , ++ j;
            cnt1 ++;
        }else {
            if(ne[j] != 0) cnt1 ++; //如果第一个字母不匹配，回到0，相当于回到1，这次不算。
            j = ne[j];
            cout << j << endl;
        }
    }
    if (j > m) return i - m;
    return 0;
}

int bf(int pos)
{
    int i = pos , j = 1;
    while(i <= n && j <= m)
    {
        if (s[i] == p[j]){
            cnt2 ++;
            ++ i , ++ j;
        }
        else {
            if (j != 1) cnt2 ++;//如果j == 1相当于没有移动
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > m) return i - m;
    return 0;
}

int main(){
    while(cin >> s + 1 >> p + 1)
    {
        n = strlen(s + 1);
        m = strlen(p + 1);
        get_next(p);
        int t = bf(1);
        int t2 = kmp(1);
        cout << "bf移动次数 :" << cnt2 << endl;
        cout << "kmp移动次数 :" << cnt1 << endl;
    }
    return 0;
}