程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 4763 Theme Section（KMP）

HDU 4763 Theme Section（KMP）

編輯：關於C++

題意：給你一個字符串s，要你求是否存在一個子串，在s的前中後各出現一次。求最大可能的子串長度。

思路：KMP變形，我們首先要了解KMP的運行機制。核心是失配函數f， f[i]表示在i點失配之後返回到f[i]這個點，且能保證f[i]之前的部分和模板串匹配。這樣的話，我們就可以利用這個特點來處理該題了。我們假設在最後一個字符處失配，那麼它將返回f[len]，那麼在f[len]之前的部分肯定是和s串的後邊f[len]個字符相匹配的。而前f[len]個字符是不用考慮的，那麼我們需要考慮的就是中間的部分是否存在一個f[len]長度的前綴串。該題因為模板串和匹配串一樣，所以很有特點，很特殊。請讀者仔細品味。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1000000 + 10;
int T,n,m,f[maxn];
char s[maxn];
void getfail(char *p, int m) {
    f[0] = f[1] = 0;
    for(int i=1;i= 3*j && _find(s+j, s, len-2*j, j)) {
                ans = j;
                break;
            }
            else j = f[j];
        }
        printf("%d\n",ans);
    }
    return 0;
}