本文主要是介绍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".
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.
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亚洲区沈阳站)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
