当前位置: 首页 > news >正文

[hdu4622 Reincarnation]后缀数组

题意:给一个长度为2000的字符串,10000次询问区间[L,R]内的不同子串的个数

思路:对原串的每个前缀求一边后缀数组,询问[L,R]就变成了询问[L,n]了,即求一个后缀里面出现了多少个不同子串。于是对所有大于等于L的后缀统计一遍即可。

 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define X                   first
#define Y                   second
#define pb                  push_back
#define mp                  make_pair
#define all(a)              (a).begin(), (a).end()
#define fillchar(a, x)      memset(a, x, sizeof(a))
#define copy(a, b)          memcpy(a, b, sizeof(a))

typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#ifndef ONLINE_JUDGE
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}
#endif
template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}
template<typename T>
void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];}
template<typename T>
void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];}

const double PI = acos(-1.0);
const int INF = 1e9 + 7;

/* -------------------------------------------------------------------------------- */

const int maxn = 2e3 + 7;

struct SA {
    //const static int maxn = 2e3 + 7;
    int sa[maxn], t[maxn], t2[maxn], c[maxn], n, m;
    int Rank[maxn], Height[maxn];
    int s[maxn];

    void init(int n, int m, char s[]) {
        for (int i = 0; i < n; i ++) this->s[i] = s[i];
        this->s[n] = 0;
        this->n = n + 1;
        this->m = m;
    }

    void build() {
        int i, *x = t, *y = t2;
        for (i = 0; i < m; i ++) c[i] = 0;
        for (i = 0; i < n; i ++) c[x[i] = s[i]] ++;
        for (i = 0; i < m; i ++) c[i] += c[i - 1];
        for (i = n - 1; i >= 0; i --) sa[-- c[x[i]]] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int p = 0;
            for (i = n - k; i < n; i ++) y[p ++] = i;
            for (i = 0; i < n; i ++) if (sa[i] >= k) y[p ++] = sa[i] - k;
            for (i = 0; i < m; i ++) c[i] = 0;
            for (i = 0; i < n; i ++) c[x[y[i]]] ++;
            for (i = 0; i < m; i ++) c[i] += c[i - 1];
            for (i = n - 1; i >= 0; i --) sa[-- c[x[y[i]]]] = y[i];
            swap(x, y);
            p = 1; x[sa[0]] = 0;
            for (i = 1; i < n; i ++) {
                x[sa[i]] = y[sa[i - 1]] == y[sa[i]] &&
                            y[sa[i - 1] + k] == y[sa[i] + k]? p - 1 : p ++;
            }
            if (p >= n) break;
            m = p;
        }
    }
    void getHeight() {
        int i, k = 0;
        for (i = 0; i < n; i ++) Rank[sa[i]] = i;
        for (i = 0; i < n; i ++) {
            if (k) k --;
            int j = sa[Rank[i] - 1];
            while (s[i + k] == s[j + k]) k ++;
            Height[Rank[i]] = k;
        }
    }
};
SA sa;
int H[maxn][maxn], S[maxn][maxn];
char s[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGE
    int T, m;
    cin >> T;
    while (T --) {
        scanf("%s", s);
        for (int i = 0; s[i]; i ++) {
            sa.init(i + 1, 128, s);
            sa.build();
            sa.getHeight();
            copy(H[i], sa.Height);
            copy(S[i], sa.sa);
        }

        cin >> m;
        while (m --) {
            int u, v;
            scanf("%d%d", &u, &v);
            int *ph = H[v - 1], *ps = S[v - 1], common = 0, ans = 0;
            u --;
            for (int i = 1; i <= v; i ++) {
                if (ps[i] >= u) {
                    ans += v - ps[i] - common;
                    common = INF;
                }
                umin(common, ph[i + 1]);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

转载于:https://www.cnblogs.com/jklongint/p/4724292.html

相关文章:

  • I学霸官方免费教程三十二:Java集合框架之Set集合
  • Spark RDD Operations(1)
  • XE3随笔7:可以省略的双引号
  • Cocos2d-x 2.3.3版本 FlappyBird
  • LeetCode Implement Stack using Queues
  • Web前端学习-第六课HTML篇
  • C# 跨线程呼叫控制
  • (13)[Xamarin.Android] 不同分辨率下的图片使用概论
  • Unity3d之流光效果
  • mysql 的 存储结构(储存引擎)
  • DP_ural_Metro
  • 手把手教你整合 SpringMvc+Spring+MyBatis+Maven
  • oracle根据pid查询出正在执行的执行语句
  • 国内最简单的短视频SDK
  • 【转】vxworks的default boot line说明
  • 「前端」从UglifyJSPlugin强制开启css压缩探究webpack插件运行机制
  • 002-读书笔记-JavaScript高级程序设计 在HTML中使用JavaScript
  • 10个确保微服务与容器安全的最佳实践
  • HTML中设置input等文本框为不可操作
  • laravel5.5 视图共享数据
  • react-native 安卓真机环境搭建
  • spring学习第二天
  • Sublime text 3 3103 注册码
  • Zepto.js源码学习之二
  • 翻译--Thinking in React
  • 分布式事物理论与实践
  • 分享几个不错的工具
  • 观察者模式实现非直接耦合
  • 基于axios的vue插件,让http请求更简单
  • 简单易用的leetcode开发测试工具(npm)
  • 解析 Webpack中import、require、按需加载的执行过程
  • 七牛云假注销小指南
  • 如何用vue打造一个移动端音乐播放器
  • 入口文件开始,分析Vue源码实现
  • 设计模式走一遍---观察者模式
  • 手机端车牌号码键盘的vue组件
  • CMake 入门1/5:基于阿里云 ECS搭建体验环境
  • # 深度解析 Socket 与 WebSocket:原理、区别与应用
  • #AngularJS#$sce.trustAsResourceUrl
  • (3)选择元素——(14)接触DOM元素(Accessing DOM elements)
  • (aiohttp-asyncio-FFmpeg-Docker-SRS)实现异步摄像头转码服务器
  • (第8天)保姆级 PL/SQL Developer 安装与配置
  • (第9篇)大数据的的超级应用——数据挖掘-推荐系统
  • (附源码)springboot金融新闻信息服务系统 毕业设计651450
  • (十五)使用Nexus创建Maven私服
  • (五)大数据实战——使用模板虚拟机实现hadoop集群虚拟机克隆及网络相关配置
  • (转)http协议
  • (转贴)用VML开发工作流设计器 UCML.NET工作流管理系统
  • .NET 中的轻量级线程安全
  • .NET/C# 利用 Walterlv.WeakEvents 高性能地定义和使用弱事件
  • .NET序列化 serializable,反序列化
  • @德人合科技——天锐绿盾 | 图纸加密软件有哪些功能呢?
  • [ 英语 ] 马斯克抱水槽“入主”推特总部中那句 Let that sink in 到底是什么梗?
  • [3300万人的聊天室] 作为产品的上游公司该如何?
  • [ASP]青辰网络考试管理系统NES X3.5