惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

The Hacker News
The Hacker News
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
P
Privacy & Cybersecurity Law Blog
C
Cybersecurity and Infrastructure Security Agency CISA
Simon Willison's Weblog
Simon Willison's Weblog
cs.CL updates on arXiv.org
cs.CL updates on arXiv.org
TaoSecurity Blog
TaoSecurity Blog
C
CERT Recently Published Vulnerability Notes
S
Security @ Cisco Blogs
Google DeepMind News
Google DeepMind News
Security Archives - TechRepublic
Security Archives - TechRepublic
T
Tenable Blog
O
OpenAI News
NISL@THU
NISL@THU
AI
AI
T
Threat Research - Cisco Blogs
Know Your Adversary
Know Your Adversary
V
Vulnerabilities – Threatpost
Schneier on Security
Schneier on Security
W
WeLiveSecurity
P
Privacy International News Feed
Cisco Talos Blog
Cisco Talos Blog
S
Secure Thoughts
D
Docker
博客园 - 三生石上(FineUI控件)
T
Troy Hunt's Blog
T
Threatpost
C
Cyber Attacks, Cyber Crime and Cyber Security
Vercel News
Vercel News
H
Hacker News: Front Page
B
Blog
S
SegmentFault 最新的问题
H
Heimdal Security Blog
T
The Blog of Author Tim Ferriss
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
G
GRAHAM CLULEY
AWS News Blog
AWS News Blog
N
News and Events Feed by Topic
L
LINUX DO - 热门话题
小众软件
小众软件
爱范儿
爱范儿
T
The Exploit Database - CXSecurity.com
Hacker News: Ask HN
Hacker News: Ask HN
Recent Announcements
Recent Announcements
Recent Commits to openclaw:main
Recent Commits to openclaw:main
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
PCI Perspectives
PCI Perspectives
I
Intezer
云风的 BLOG
云风的 BLOG
P
Proofpoint News Feed

博客园 - ZefengYao

Markdown 入门与 Word 使用指南 关于崩溃报告的日志以及dump文件 hdu 6223 Infinite Fraction Path 2017南宁现场赛E The Champion ACM-ICPC 2018 南京赛区网络预赛 Sum c语言几个字符串处理函数的简单实现 各种类型排序的实现及比较 随机洗牌算法Knuth Shuffle和错排公式 两个栈实现队列 面试杂题 面试题——栈的压入、弹出顺序 C++ 智能指针的简单实现 openGL初学函数解释汇总 foj Problem 2107 Hua Rong Dao foj Problem 2282 Wand UVA-1400 Ray, Pass me the dishes! Uva 11174 Stand in a Line UVA 11375 Matches poj 3729 Facer’s string
《挑战程序设计竞赛》 利用后缀数组求最长回文串
ZefengYao · 2018-05-29 · via 博客园 - ZefengYao

问题:求一个字符串的最长回文子串。

解决方案:利用后缀数组,设这个字符串是S,S'是这个字符串的反转,设T=S+'$'+S',则所有的回文子串一定会出现在字符串T当中的其中两个后缀的前缀上,所以只要求T的lcp,利用lcp求后缀之间的相同前缀的最大长度。

代码参考:

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N_MAX = 100000 + 20;
typedef long long ll;
int n, k;
int Rank[N_MAX * 2];
int tmp[N_MAX * 2];
int sa[N_MAX * 2];
int lcp[N_MAX * 2];
bool compare_sa(const int& i, const int& j) {
    if (Rank[i] != Rank[j])return Rank[i] < Rank[j];
    else {
        int ri = i + k <= n ? Rank[i + k] : -1;
        int rj = j + k <= n ? Rank[j + k] : -1;
        return ri < rj;
    }
}

void construct_sa(const string& S, int *sa) {
    n = S.size();
    for (int i = 0; i <= n; i++) {
        sa[i] = i;
        Rank[i] = i < n ? S[i] : -1;
    }
    for (k = 1; k <= n; k *= 2) {
        sort(sa, sa + n + 1, compare_sa);
        tmp[sa[0]] = 0;
        for (int i = 1; i <= n; i++) {
            tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
        }
        for (int i = 0; i <= n; i++) {
            Rank[i] = tmp[i];
        }
    }
}
void construct_lcp(const string& S, int *sa, int *lcp) {
    memset(lcp, 0, sizeof(lcp));
    int n = S.length();
    for (int i = 0; i <= n; i++)Rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for (int i = 0; i < n; i++) {
        int j = sa[Rank[i] - 1];
        if (h > 0)h--;
        for (; j + h < n&&i + h < n; h++) {
            if (S[j + h] != S[i + h])break;
        }
        lcp[Rank[i] - 1] = h;
    }
}

int min_lcp[N_MAX * 2];
void rmq_init(int k, int l, int r) {//节点k的区间[l,r)
    if (r <= l)return;
    if (r - l == 1) {
        min_lcp[k] = lcp[l];
    }
    else {
        int chl =2*k + 1, chr = 2*k + 2;
        int mid = (l + r) >> 1;
        rmq_init(chl, l, mid);
        rmq_init(chr, mid, r);
        min_lcp[k] = min(min_lcp[chl], min_lcp[chr]);
    }
}

int query_rmq(int a, int b, int k, int l, int r) {
    if (b <= l || a >= r) {
        return INF;
    }
    else if (a <= l&&b >= r) {
        return min_lcp[k];
    }
    else {
        int mid = (l + r) >> 1;
        int min_L = query_rmq(a, b,2*k + 1, l, mid);
        int min_R = query_rmq(a, b, 2*k + 2, mid, r);
        return min(min_L, min_R);
    }
}

string s;
int main() {
    while (cin >> s) {
        int N = s.size();
        string T = s;
        reverse(T.begin(), T.end());
        s += '$' + T;
        n = s.size();
        construct_sa(s, sa);
        construct_lcp(s, sa, lcp);
        for (int i = 0; i <= s.size(); i++)Rank[sa[i]] = i;
        rmq_init(0,0,s.size()+1);
        int ans = 0;
        for (int i = 0; i < N; i++) {
            int j = 2 * N - i;
            int l = query_rmq(min(Rank[i], Rank[j]), max(Rank[i], Rank[j]), 0, 0, s.size()+1);
            cout <<"l:"<< l << endl;
            ans = max(ans,2*l-1);
        }
        for (int i = 1; i < N;i++) {
            int j = 2 * N - i + 1;
            int l = query_rmq(min(Rank[i], Rank[j]), max(Rank[i], Rank[j]), 0, 0, s.size()+1);
            cout << "l:" << l << endl;
            ans = max(ans, 2 * l);
        }
        printf("%d\n",ans);
    }
    return 0;
}
//mississippi