HDU 5510 Bazinga 字符串HASH (2015ACM/ICPC亚洲区沈阳站)

本文主要是介绍HDU 5510 Bazinga 字符串HASH (2015ACM/ICPC亚洲区沈阳站)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】：click here~~

【题目大意】：

Bazinga

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 39 Accepted Submission(s): 15

Problem Description

Ladies and gentlemen, please sit up straight.
Don't tilt your head. I'm serious.

For

n given strings

S1,S2,⋯,Sn , labelled from

1 to

n , you should find the largest

i (1≤i≤n) such that there exists an integer

j (1≤j<i) and

Sj is not a substring of

Si .

A substring of a string

Si is another string that occurs in

Si . For example, ``ruiz" is a substring of ``ruizhang", and ``rzhang" is not a substring of ``ruizhang".

Input

The first line contains an integer

t (1≤t≤50) which is the number of test cases.
For each test case, the first line is the positive integer

n (1≤n≤500) and in the following

n lines list are the strings

S1,S2,⋯,Sn .
All strings are given in lower-case letters and strings are no longer than

2000 letters.

Output

For each test case, output the largest label you get. If it does not exist, output

−1 .

Sample Input

  4
5
ab
abc
zabc
abcd
zabcd
4
you
lovinyou
aboutlovinyou
allaboutlovinyou
5
de
def
abcd
abcde
abcdef
3
a
ba
ccc

Sample Output

  Case #1: 4
Case #2: -1
Case #3: 4
Case #4: 3

求前i个字符串不是该i字符串的子串的最大的i值

【思路】暴力KMP，暴力字符串HASH

此处留坑代填~~

先放挫挫代码：

/*
* Problem: HDU No.5510
* Running time: 399MS
* Complier: G++
* Author: javaherongwei
* Create Time: 17:30 2015/10/31 星期六
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef unsigned long long LLU;
const LLU base=1e9+7;
const int N=505;
const int M=2020;
char s[N][M];
LLU f[N][M], fac[M];
vector<int> val;
int n, len[N];
LLU get(int i, int l, int r)
{return f[i][r]-f[i][l-1]*fac[r-l+1];
}
bool check(int x, int y)
{if(len[y]>len[x]) return false;for(int i = len[y]; i <= len[x]; i++){if(f[y][len[y]] == get(x,i-len[y]+1,i)) return true;}return false;
}
int solve()
{for(int i = 0; i < n; i++){len[i] = strlen(s[i]+1);f[i][0] = 0;for(int j = 1; j <= len[i]; j++){f[i][j] = f[i][j-1]*base+s[i][j]-'a'+1;}}int ans = -1;val.clear();val.push_back(0);for(int i = 1; i < n; i++){while(val.size()){if(check(i, val[val.size()-1])){val.pop_back();}else  break;}val.push_back(i);if(val.size()>1) ans = i+1;}return ans;
}
void init()
{fac[0] = 1;for(int i = 1; i <= 2002; i++) fac[i] = fac[i-1]*base;
}
int main()
{//freopen("1.txt","r",stdin);init();int t, tot = 0;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; i++) scanf("%s", s[i]+1);printf("Case #%d: %d\n", ++tot, solve());}return 0;
}

这篇关于HDU 5510 Bazinga 字符串HASH (2015ACM/ICPC亚洲区沈阳站)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！