Find the suffix array , And then two answers , Yes height Array grouping test answers . Time complexity O(|S| log|S|)

--------------------------------------------------------------------------------

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
 
using namespace std;
 
const int maxn = 1009;
const int maxN = 1000009;
 
inline int read() {
char c = getchar();
for(; !isdigit(c); c = getchar());
int ret = 0;
for(; isdigit(c); c = getchar())
ret = ret * 10 + c - '0';
return ret;
}
 
bool vis[maxn];
int str[maxn][maxn], len[maxn], n, Top;
int S[maxN], Id[maxN], stk[maxN], N;
int cnt[maxN], Sa[maxN], Height[maxN], Rank[maxN];
 
void Build(int m) {
int *x = Height, *y = Rank;
for(int i = 0; i < m; i++) cnt[i] = 0;
for(int i = 0; i < N; i++) cnt[x[i] = S[i]]++;
for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(int i = N; i--; ) Sa[--cnt[x[i]]] = i;
for(int k = 1, p = 0; k <= N; k <<= 1, p = 0) {
for(int i = N - k; i < N; i++) y[p++] = i;
for(int i = 0; i < N; i++)
if(Sa[i] >= k) y[p++] = Sa[i] - k;
for(int i = 0; i < m; i++) cnt[i] = 0;
for(int i = 0; i < N; i++) cnt[x[y[i]]]++;
for(int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for(int i = N; i--; ) Sa[--cnt[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[Sa[0]] = 0;
for(int i = 1; i < N; i++) {
if(y[Sa[i]] != y[Sa[i - 1]] || y[Sa[i] + k] != y[Sa[i - 1] + k]) p++;
x[Sa[i]] = p - 1;
}
if(p >= N) break;
m = p;
}
for(int i = 0; i < N; i++) Rank[Sa[i]] = i;
Height[0] = 0;
for(int i = 0, h = 0; i < N; i++) if(Rank[i]) {
if(h) h--;
while(S[i + h] == S[Sa[Rank[i] - 1] + h]) h++;
Height[Rank[i]] = h;
}
}
 
void Init() {
int mn = 1 << 30, mx = -1 << 30;
n = read();
for(int i = 0; i < n; i++) {
len[i] = read();
for(int j = 0; j < len[i]; j++) str[i][j] = read();
for(int j = len[i]; --j; ) {
str[i][j] -= str[i][j - 1];
mn = min(mn, str[i][j]);
mx = max(mx, str[i][j]);
}
}
N = 0;
for(int i = 0; i < n; i++) {
for(int j = 1; j < len[i]; j++) {
S[N] = str[i][j] - mn + n;
Id[N++] = i;
}
S[N] = n - i - 1;
Id[N++] = n;
}
Build(mx - mn + n + 1);
memset(vis, 0, sizeof vis);
vis[n] = 1;
Top = 0;
}
 
bool chk(int v) {
while(Top) vis[stk[--Top]] = 0;
for(int i = 1; i < N; i++) if(Height[i] >= v) {
if(!vis[Id[Sa[i - 1]]])
vis[stk[Top++] = Id[Sa[i - 1]]] = 1;
if(!vis[Id[Sa[i]]])
vis[stk[Top++] = Id[Sa[i]]] = 1;
if(Top >= n) return true;
} else {
while(Top) vis[stk[--Top]] = 0;
}
return false;
}
 
void Work() {
int l = 1, r = maxN, ans = 0;
while(l <= r) {
int m = (l + r) >> 1;
if(chk(m)) {
ans = m, l = m + 1;
}
else
r = m - 1;
}
printf("%d\n", ++ans);
}
 
int main() {
Init();
Work();
return 0;
}

--------------------------------------------------------------------------------

SDOI2008 Sandy The card of ( The suffix array ) More articles about

  1. 【BZOJ4698】Sdoi2008 Sandy The card of The suffix array +RMQ

    [BZOJ4698]Sdoi2008 Sandy The card of Description Sandy and Sue They are keen on collecting cards in the noodles . However ,Sue I collect cards because of the beautiful characters on them , and Sandy It's to save the card ...

  2. 【bzoj4698】[Sdoi2008] Sandy The card of The suffix array

    Title Description Sandy and Sue They are keen on collecting cards in the noodles . However ,Sue I collect cards because of the beautiful characters on them , and Sandy It's to save cards for flashy character models . Each card is marked by a number , The first i Sequence of cards ...

  3. BZOJ 4698: Sdoi2008 Sandy The card of The suffix array + RMQ + Score checking

    Title Description Sandy and Sue They are keen on collecting cards in the noodles . However ,Sue I collect cards because of the beautiful characters on them , and Sandy It's to save cards for flashy character models . Each card is marked by a number , The first i It's a card ...

  4. BZOJ4698: Sdoi2008 Sandy The card of ( The suffix array Two points )

    The question Topic link Sol Don't ask me why I sent two articles blog, Just to cheat the traffic Suffix array is also better , Let's make a difference between all the positions , And then in height Two parts in the array Good data // luogu-judger-enab ...

  5. BZOJ 4698: Sdoi2008 Sandy The card of ( The suffix array + Difference + Two points answer )

    Portal Their thinking See a substring add a number to another substring , Naturally, we can think of difference . Then put all the strings together , Find out \(height\) After the array, you can divide the answer into two parts , One answer in half at a time, and then count the number of consecutive answers \(height> ...

  6. Luogu P2463 [SDOI2008]Sandy The card of ( The suffix array SA + Difference + Two points answer )

    Topic link :https://www.luogu.org/problem/P2463 [ The question ] Find out N The longest length of the same substring that appears in all strings , The definition of the same substring is as follows : All elements add one number to make another , The two strings are the same , can ...

  7. 【BZOJ-4698】Sandy The card of The suffix array

    4698: Sdoi2008 Sandy The card of Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 140  Solved: 55[Submit][Stat ...

  8. BZOJ 4698: Sdoi2008 Sandy The card of [ Postfix automaton ]

    4698: Sdoi2008 Sandy The card of The question : The difference is followed by multiple strings LCS SAM+map Dafa is good Wrong template intelligence -2 #include <iostream> #include <c ...

  9. LG2463/BZOJ4698 「SDOI2008」Sandy The card of The suffix array

    Problem description LG2463 BZOJ4698 Answer key notice \(n\) Number of strings , It wasn't easy to deal with at first , It's easy to think of putting this \(n\) The numbers are linked together , Form a large string , But it's not easy to deal with each string . After thinking , Think of it in the middle of each string ...

Random recommendation

  1. Use ASP.NET MVC、Rabbit WeixinSDK and Azure Rapid development and deployment of wechat background

    ( This article is also published in my official account of WeChat "dotNET Daily essays ", Welcome to the QR code on the right .) . : The official account system and data are basically ready. , You can share how I developed the background system of WeChat official account. ...

  2. 2016 Multi-University Training Contest 8

    solved 4/11 2016 Multi-University Training Contest 8 greedy 1001 Ball(BH) Code : #include <bits/stdc++.h ...

  3. Android Sharing files Runtime jurisdiction

    Developing Android When applied , It's always about getting on the phone . Location . Access to sensitive user information such as network , stay Android in , Contacts . The current location and other sensitive information are provided by permissions The protection of ,Android ...

  4. 【HDOJ】2054 A == B ？

    At first, this topic is not easy to understand ,so easy. Look again. ac rate , Notice that the variable type is not specified . It's obviously a string problem . You need to consider +/- Sign bit ,+.1.-.1.00010.0.+0.-00.00 , etc. , At the same time, the array is turned on 100000 With ...

  5. [2017-08-21]Abp series —— How to use Abp Plug-in mechanism ( Registration rights 、 menu 、 route )

    The catalogue of this series :Abp Introduction and experience sharing - Catalog Abp The module system supports plug-in mechanism , You can place module assemblies in the specified directory , The directory is then searched when the application starts , Load all the modules in the assembly . How to use this mechanism for plug-in development ? ...

  6. take Excel Thousands of data are written to the database

    Brief description : Due to work needs , Need one Excel All data in the table is imported into the database . The following table , Of course, that's only part of it , More than a thousand in all . Pre treatment : First of all, make sure that the Excel The data in the table cannot be empty , If there is empty data , It can be a little bit ...

  7. Django And --POST Method to process the form request

    Last one :Django And --MVC Of Model  Demonstrates how to use GET Method to process the form request , This article talks about returning results directly on the current page , And use the more commonly used POST Method treatment . One . First of all, let's revise page.html <!D ...

  8. The embedded - Xunwei iTOP-4418/6818 Development board compilation Android Image technology sharing

    Xunwei is based on Ubuntu12.04.2 Platform development , All configuration and compilation scripts are also based on this platform . If you are right about Linux and Android I'm familiar with development , I believe you will find out the cause and solve it step by step according to the error prompts , The error prompt is generally the selected platform ...

  9. Ajax take PHP JSON Data and display

    <!DOCTYPE html> <html lang="zh"> <head> <meta charset="UTF-8&quo ...

  10. Ecshop Table structure order_info

    CREATE TABLE IF NOT EXISTS `ecs_order_info` (  `order_id` mediumint(8) unsigned NOT NULL AUTO_INCREM ...