【CAIOJ1177】 子串是否出现

【题目链接】

           点击打开链接

【算法】

          KMP

【代码】

           

#include<bits/stdc++.h>
using namespace std;
#define MAXA 1000010
#define MAXB 1010

int i,j,lenA,lenB;
int p[MAXB];
char SA[MAXA],SB[MAXB];

int main() {
        
        scanf("%s",SA+1); lenA = strlen(SA+1);
        scanf("%s",SB+1); lenB = strlen(SB+1);
        p[1] = 0;
        for (i = 2; i <= lenB; i++) {
                j = p[i-1];
                while ((j > 0) && (SB[i] != SB[j+1])) j = p[j];
                if (SB[i] == SB[j+1]) p[i] = j + 1; 
                else p[i] = 0;
        }
        
        j = 0;
        
        for (i = 1; i <= lenA; i++) {
                while ((j > 0) && (SA[i] != SB[j+1])) j = p[j];
                if (SA[i] == SB[j+1]) j++;
                if (j == lenB) {
                        cout<< i - lenB + 1 << ' ' << i << endl;
                        exit(0);
                }    
        }
        
        cout<< "NO" << endl;
        
        return 0;
    
}