程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4763 Theme Section(KMP)

HDU 4763 Theme Section(KMP)

編輯:C++入門知識

HDU 4763 Theme Section(KMP)


題意:給你一個字符串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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved