http://acm.hdu.edu.cn/showproblem.php?pid=5769

The question : stay S Find out from the string X The number of different substrings that appear in the string ? among 1 <= |S| < $10^5$

Official explanation : Process the... In the suffix array sa[] Array and height[] Array . Without considering the inclusion of characters X Under the circumstances , The number of different substrings is

If characters are required X, Just record the distance sa[i] Recent characters X The location of ( use nxt[sa[i]] Express ) that will do , Number

understand : The suffix array height[i] Namely sa[i] And sa[i-1] Of LCP, Solve all the different substrings in the suffix array ( I've only written before SAM Dealing with all the different substrings ..) It's better to understand , There must be substrings in the string x when , It needs to be done first kmp Find all the matching positions , At the end of the process i When there is a suffix , take max It means that it must contain X, And different substrings ;

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define pb push_back
#define MK make_pair
#define A first
#define B second
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define bitnum(a) __builtin_popcount(a)
#define lowbit(x) (x&(-x))
#define clear0 (0xFFFFFFFE)
#define mod 1000000007
#define K(x) ((x)*(x))
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
void read1(T &m)
{
T x = ,f = ;char ch = getchar();
while(ch <'' || ch >''){ if(ch == '-') f = -;ch=getchar(); }
while(ch >= '' && ch <= ''){ x = x* + ch - '';ch = getchar(); }
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
inline ll gcd(ll a,ll b){ return b == ? a: gcd(b,a%b); }
template<class T1, class T2> inline void gmax(T1& a, T2 b){ if(a < b) a = b;}
template<class T1, class T2> inline void gmin(T1& a, T2 b){ if(a > b) a = b;}
const int maxn = ;
int sa[maxn], t[maxn],t2[maxn],c[maxn],w[maxn];
int cmp(int *r,int a,int b,int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void build_sa(char *r,int n,int m)
{
int i, j, p, *x = t, *y = t2;
for(i = ; i < m;i++) c[i] = ;
for(i = ; i < n;i++) c[x[i] = r[i]]++;
for(i = ; i < m;i++) c[i] += c[i-];
for(i = n-; i >= ; i--) sa[--c[x[i]]] = i; for(j = , p = ; p < n; j <<= , m = p){
for(p = , i = n - j; i < n;i++) y[p++] = i;
for(i = ; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j;
for(i = ; i < n; i++) w[i] = x[y[i]];
for(i = ; i < m; i++) c[i] = ;
for(i = ; i < n; i++) c[w[i]]++;
for(i = ; i < m; i++) c[i] += c[i-];
for(i = n-; i >= ; i--) sa[--c[w[i]]] = y[i];
swap(x,y);
for(p = , x[sa[]] = , i = ; i < n; i++)
x[sa[i]] = cmp(y, sa[i-], sa[i], j)? p-: p++;
if(p >= n) break;
m = p;
}
}
char S[maxn], X[maxn];
int height[maxn], rk[maxn];
void getHeight(int n)
{
for(int i = ; i<= n; i++) rk[sa[i]] = i;
for(int i = , j, k = ; i < n; height[rk[i++]] = k)
for(k? k--:, j = sa[rk[i] - ]; S[i+k] == S[j+k]; k++);
} int f[maxn];
void getfail(char *p)
{
f[] = f[] = ;
int n = strlen(p);
for(int i = ;i < n;i++){
int j = f[i];
if(j && p[i] != p[j]) j = f[j];
f[i+] = (p[i] == p[j] ?j+:);// i+1 It's going to recurs to the next n position
}
}
vector<int> vec;
void Find(char *T, char *p)
{
vec.clear();
ll j = ,n = strlen(T),m = strlen(p);
for(int i = ;i < n;i++){
while(j && T[i] != p[j]) j = f[j];
if(T[i] == p[j]) j++;
if(j == m){
vec.pb(i);
j = ;
i -= m-;
}
}
sort(vec.begin(), vec.end());
} int main()
{
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T, kase = ;
scanf("%d",&T);
while(T--){
scanf("%s%s", X, S);
int len = strlen(S), m = strlen(X);
S[len] = '#';S[len+] = ;
build_sa(S,len+,'z'+);
getHeight(len); getfail(X);
Find(S,X);
vec.pb(len);
ll ans = ;
rep1(i,,len){
if(sa[i]+m- > len) continue;
int nxt = lower_bound(vec.begin(), vec.end(), sa[i]+m-) - vec.begin();
ans += len - max(vec[nxt],sa[i] + height[i]);
}
printf("Case #%d: %lld\n", kase++, ans);
}
return ;
}

hdu 5769 Substring The suffix array + KMP More articles about

  1. HDU 5769 Substring The suffix array

    Substring Problem Description ?? is practicing his program skill, and now he is given a string, he h ...

  2. HDU 5679 Substring Suffix array weight determination

    The question : Find out how many different inclusions there are in the parent string x Substrings of characters analysis :( First of all FZU Official explanation ) The question above is SPOJ694 , In fact, the two questions are the same , Principle every time from small to large scan suffix sa Array , Add some prefixes to the new current suffix , And subtract the duplicate ...

  3. hdu5442(2015 Changchun District network competition 1006) The suffix array +KMP / Minimum representation ?

    The question : Given a length of lowercase letters is n String , end to end , You can start with any character , Take this string clockwise or counterclockwise ( The length is n), Find the starting character position and clockwise or counterclockwise of a string with the largest dictionary order . If there are more than one dictionary, the order is the largest ...

  4. HDU 5769 Substring( The suffix array )

    [ Topic link ] http://acm.hdu.edu.cn/showproblem.php?pid=5769 [ The main idea of the topic ] Find the number of substrings containing letters in a string , As long as there is a substring with unequal characters, it can be regarded as different ...

  5. hdu 1403 Longest Common Substring The suffix array The template questions

    Topic link The question Ask the longest common substring of two strings . Ideas Add a special character and put it together , Find the suffix array and \(height\) Array . Scan once and you'll get the answer , Pay attention to judge whether the starting point is in two strings respectively . Code #include ...

  6. POJ3080 POJ3450Corporate Identity( Generalized suffix automata || The suffix array ||KMP)

    Beside other services, ACM helps companies to clearly state their “corporate identity”, which includ ...

  7. POJ3693 Maximum repetition substring [ The suffix array ST surface ]

    Maximum repetition substring Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9458   Acc ...

  8. UVA 11475 The suffix array /KMP

    Topic link : The question : Given a string containing only letters , Add as few characters as possible at the end of the string to make the string palindrome string . Ideas : Because you can only add characters from the end , So what we're looking for is the longest suffix palindrome string . Then the character added is the longest suffix palindrome in addition to the original string ...

  9. POJ 3450 The suffix array /KMP

    Topic link :http://poj.org/problem?id=3450 The question : Given n A string , seek n The longest common substring of a string , No solution output IDENTITY LOST, Otherwise, the longest common substring . When there are multiple solutions, the output dictionary order is the most ...

Random recommendation

  1. How to write complex SQL

    I'm often asked about the very complicated sql How it was written , I never know how to answer .         Because even though I write like this sql Very comfortable , But I don't know how to tell others how to write . Many people attribute the problem to talent , I don't think so , I ...

  2. Android in BroadcastReceiver radio broadcast

    BroadCastReceiver brief introduction Broadcast receivers ( BroadcastReceiver ) For receiving broadcast Intent , radio broadcast Intent Is sent by calling Context.sendBroadca ...

  3. WindowsPhone 8 Development And Local database application

    There is an example of a local database provided by Microsoft  http://code.msdn.microsoft.com/wpapps/Local-Database-Sample-57b1614c It can be referenced . The core of it is ...

  4. XJOI Online synchronous training DAY5 T1

    Ideas : Consider it , The final set must be gcd=1 Set , So let's enumerate n Which of the numbers must be chosen , And then we decompose it into prime factors , Because the prime number will not exceed 9 individual , State compression is possible , To get a state of 0 Of dp The value is the answer . #include<c ...

  5. openstack controller ha Test environment construction record ( 5、 ... and )—— To configure rabbitmq colony

    To configure rabbitmq The steps of clustering are very simple , Because it has cluster function , Reference resources openstack Official document :http://docs.openstack.org/ha-guide/controller-ha-rabb ...

  6. WeChat official account development notes 2(nodejs)

    This article mainly records all kinds of calls to wechat api And function realization One . Began in access_token No matter what wechat calls api, You need a query parameter , That's what we do every other day 1 Hour or 2 Hours access_token, note 1 It's guaranteed in the book ...

  7. mysql Change the data store directory

    Please refer to the article for details 1.http://blog.csdn.net/aaronbai/article/details/1431190 When you change the data store directory ERROR 2002 (HY000): ...

  8. 20135202 Yan Jiaxin --week3 Tracking analysis Linux The startup process of the kernel -- Experiment and summary

    Experiment three : Tracking analysis Linux The startup process of the kernel One . The debugging steps are as follows : Use gdb Trace debug kernel qemu -kernel linux-3.18.6/arch/x86/boot/bzImage -initrd r ...

  9. 2018.11.7 About Web The project is deployed to Alibaba cloud server -5 It's a two-step process

    take Eclipse Derived War Deploy the package to Alibaba cloud server , Provide real-time access to mobile terminals 1. First log in to alicloud website to register an account , Select the server type ( I use it Cloud server ECS), If you are still a college student, you can enjoy a discount , The lowest seems to be 9 ...

  10. GlusterFS Distributed file system deployment

    GlusterFS Is a scalable network file system , Using common off the shelf hardware , You can create large distributed storage streaming solutions . Data analysis . Tasks related to other data .GlusterFS It's free and open source software . Please refer to the official website for details :http ...