SCU 4438 Censor(KMP / HASH)

여과 민감 어
사실은 꼬치 를 찾 는 거 예요. 그냥 답 을 기록 할 때 가 달라 요.
스 택 과 유사 한 용기 로 일치 하 는 것 을 기록 하면 됩 니 다.  일치 하 는 스 택 n 개 를 만 나 면 됩 니 다.
KMP 는 창 고 를 나 간 후 이전의 매 칭 을 계속 할 수 있 도록 여러 배열 기록 스 택 에 있 는 현재 요소 의 배치 위 치 를 기록 합 니 다.  -  -
KMP:
#include 
using namespace std;
const int MAXN = 5e6+10;
struct KMP
{
    int f[MAXN];
    void getFail(char S[])
    {
        int i=0,j=-1;
        int len=strlen(S);
        f[0]=-1;
        while (i

HASH:
#include 
using namespace std;
typedef unsigned long long ULL;
const int MAXN  = 5e6+100;
const int SEED = 13331;

ULL ht[MAXN],hs;
ULL xl[MAXN];
char s[MAXN],t[MAXN],ans[MAXN];
int main()
{
    xl[0]=1;
    for(int i=1;i=n&&ht[top]-ht[top-n]*xl[n]==hs)
                top-=n;
        }
        for(int i=0;i

좋은 웹페이지 즐겨찾기