Common Substrings POJ - 3415(접미사 로봇)

Common Substrings

\[ Time Limit: 5000 ms\quad Memory Limit: 65536 kB\]

제목의 뜻

두 문자열의 공통 하위 문자열 길이가\(k\) 대수보다 작지 않도록 하려면 두 문자열을 입력합니다.

사고의 방향

\(S\)열에 접미사 자동기를 구축한 다음\(v\in u'son\),\(dp[u] + = dp[v]\)로 각 노드의\(endpos\) 크기를 구한다.
\(T\) 열을 사용하여 로봇에서 가장 긴 공통 연속 서브열을 달립니다. 현재\(T\) 열에 일치하는 가장 긴 부분이\(t\)라고 가정하고 로봇의\(p\) 노드에 멈춥니다.중복 계수를 방지하기 위해서, 현재 요청한\(t\) 의 모든 접미사가\(S\) 에 일치하는 위치가 얼마나 됩니까?
이 계산 방법은\(\sum dp[i]*(LCS-max(k-1,father.len)))\)입니다.\(p\) 노드에서\(LCS\) 는 매번 업데이트하는 답안\(res\) 이고, 다음에\(p\) 의\(father\) 로 업데이트할 때\(LCS\) 는\(i.len\) 이다.
예를 들어 샘플의\(xx\xx\) 두 번째 열이 일치할 때\(x\) 에 처음 일치합니다.\(xx\)와 두 번째 일치한 다음\업데이트를 계속합니다.(x\)에 대한 대답입니다.
그러나 매번 상향 업데이트를 폭력적으로 하면 시간이 초과됩니다. 방금 일치한\(p\) 노드의 답은\(res\) 와 관계가 있고\(p\) 상향 업데이트된 노드의 공헌은 고정되어 있기 때문에 모든\(p\) 노드의 공헌을 구한 다음에\(cnt[i]\) 노드가 아래에서 몇 번 업데이트되었는지 거꾸로 계산하고 업데이트 횟수를 줄일 수 있습니다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define  lowbit(x)  x & (-x)
#define  mes(a, b)  memset(a, b, sizeof a)
#define  fi         first
#define  se         second
#define  pii        pair
#define  INOPEN     freopen("in.txt", "r", stdin)
#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;
typedef long long int ll;
const int    maxn = 2e5 + 10;
const int    maxm = 1e5 + 10;
const ll     mod  = 1e9 + 7;
const ll     INF  = 1e18 + 100;
const int    inf  = 0x3f3f3f3f;
const double pi   = acos(-1.0);
const double eps  = 1e-8;
using namespace std;

int n, m, k;
int cas, tol, T;

struct Sam {
    struct Node {
        int next[55];
        int fa, len;
        void init() {
            mes(next, 0);
            fa = len = 0;
        }
    } node[maxn];
    ll dp[maxn], cnt[maxn];
    int sz, last;
    void init() {
        last = sz = 1;
        mes(dp, 0);
        node[sz].init();
    }
    void insert(int k) {
        int p = last, np = last = ++sz;
        dp[np] = 1;
        node[np].init();
        node[np].len = node[p].len+1;
        for(; p&&!node[p].next[k]; p=node[p].fa)
            node[p].next[k] = np;
        if(p == 0) {
            node[np].fa = 1;
        } else {
            int q = node[p].next[k];
            if(node[q].len == node[p].len+1) {
                node[np].fa = q;
            } else {
                int nq = ++sz;
                node[nq] = node[q];
                node[nq].len = node[p].len+1;
                node[np].fa = node[q].fa = nq;
                for(; p&&node[p].next[k]==q; p=node[p].fa)
                    node[p].next[k] = nq;
            }
        }
    }
    int tax[maxn], gid[maxn];
    void handle() {
        for(int i=0; i<=sz; i++)    tax[i] = cnt[i] = 0;
        for(int i=1; i<=sz; i++)    tax[node[i].len]++;
        for(int i=1; i<=sz; i++)    tax[i] += tax[i-1];
        for(int i=1; i<=sz; i++)    gid[tax[node[i].len]--] = i;
        for(int i=sz; i>=1; i--) {
            int u = gid[i];
            int fa = node[u].fa;
            dp[fa] += dp[u];
        }
    }
    void solve(char *s, int k) {
        int len = strlen(s+1);
        int p = 1;
        ll res = 0, ans = 0;
        for(int i=1; i<=len; i++) {
            int nst;
            if('a'<=s[i] && s[i]<='z')  nst = s[i]-'a'+1;
            else    nst = s[i]-'A'+1+26;
            while(p && !node[p].next[nst]) {
                p = node[p].fa;
                res = node[p].len;
            }
            if(p == 0) {
                p = 1;
                res = 0;
            } else {
                p = node[p].next[nst];
                res++;
            }
            if(res >= k) {
                ans += dp[p]*(res - max(node[node[p].fa].len, k-1));
                if(node[node[p].fa].len >= k)
                    cnt[node[p].fa]++;
            }
        }
        for(int i=sz; i>=1; i--) {
            int u = gid[i];
            ans += dp[u]*cnt[u]*(node[u].len - max(node[node[u].fa].len, k-1));
            if(node[node[u].fa].len >= k)
                cnt[node[u].fa] += cnt[u];
        }
        printf("%lld
", ans);
    }
} sam;
char s[maxn], t[maxn];

int main() {
    while(scanf("%d", &k), k) {
        sam.init();
        scanf("%s%s", s+1, t+1);
        int slen = strlen(s+1);
        for(int i=1; i<=slen; i++) {
            int nst;
            if('a'<=s[i] && s[i]<='z')  nst = s[i]-'a'+1;
            else    nst = s[i]-'A'+1+26;
            sam.insert(nst);
        }
        sam.handle();
        sam.solve(t, k);
    }
    return 0;
}

전재 대상:https://www.cnblogs.com/Jiaaaaaaaqi/p/10953056.html

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Common Substrings POJ - 3415(접미사 로봇)