# 14188: 【原4188】罪恶黑名单

### 题目描述

author: DS TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4188

2
goodluck
goodluck
1
1 1

no

## Neight99's solution

#include <iostream>
#include <string>

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

const int maxN = 1e5 + 10;
string str[maxN];
int preHashpos[maxN] = {0}, sufHashpos[maxN] = {0};
ull strHash[maxN], preHash1[maxN] = {0}, sufHash1[maxN] = {0};

ull calHash(string str, int l, int r) {
ull ans = 0;
for (int i = l; i < r; i++) {
ans = 131 * ans + (str[i] - 'a' + 1);
}
return ans;
}

void preHash(string str, ull *preHash) {
preHash[0] = str[0] - 'a' + 1;
for (int i = 1; i < str.length(); i++) {
preHash[i] = 131 * preHash[i - 1] + (str[i] - 'a' + 1);
}
}

void sufHash(string str, ull *preHash) {
int len = str.length();
preHash[0] = str[len - 1] - 'a' + 1;
for (int i = 1; i < len; i++) {
preHash[i] = 131 * preHash[i - 1] + (str[len - i - 1] - 'a' + 1);
}
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int N, M, order, x, y;

cin >> N;
str[0] = "";
for (int i = 1; i <= N; i++) {
cin >> str[i];
strHash[i] = calHash(str[i], 0, str[i].length());
preHashpos[i] = preHashpos[i - 1] + str[i - 1].length();
sufHashpos[i] = sufHashpos[i - 1] + str[i - 1].length();
preHash(str[i], &preHash1[preHashpos[i]]);
sufHash(str[i], &sufHash1[sufHashpos[i]]);
}

cin >> M;
for (int i = 0; i < M; i++) {
cin >> order;
switch (order) {
case 1: {
cin >> x;
bool flag = 0;
for (int i = 1; i < x; i++) {
if (strHash[i] == strHash[x]) {
flag = 1;
break;
}
}
if (flag) {
cout << "yes" << '\n';
} else {
cout << "no" << '\n';
}
break;
}
case 2: {
cin >> x >> y;
int len1 = str[x].length(), len2 = str[y].length(),
len3 = len1 < len2 ? len1 : len2;
int l = 0, r = len3 - 1, ans;
ull *temp1 = &preHash1[preHashpos[x]],
*temp2 = &preHash1[preHashpos[y]];
while (l <= r) {
int mid = (l + r) >> 1;
if (temp1[mid] == temp2[mid]) {
ans = mid + 1;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << '\n';
break;
}
case 3: {
cin >> x >> y;
int len1 = str[x].length(), len2 = str[y].length(),
len3 = len1 < len2 ? len1 : len2;
int l = 0, r = len3 - 1, ans;
ull *temp1 = &sufHash1[sufHashpos[x]],
*temp2 = &sufHash1[sufHashpos[y]];
while (l <= r) {
int mid = (l + r) >> 1;
if (temp1[mid] == temp2[mid]) {
ans = mid + 1;
l = mid + 1;
} else {
r = mid - 1;
}
}
cout << ans << '\n';
break;
}
}
}
return 0;
}

## victrid's solution

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int
total;

unsigned long long
len[1000005]   = {0},
fhash[1000005] = {0},
bhash[1000005] = {0},
shash[1000005] = {0};

char
buffer[1000005];

int main() {
scanf("%d", &total);
for (int i = 1; i <= total; i++) {
scanf("%s", buffer);
int s             = strlen(buffer);
len[i]            = s + len[i - 1];
fhash[len[i - 1]] = buffer[0];
bhash[len[i] - 1] = buffer[s - 1];
for (int j = 1; j < s; j++) {
//...Hash number...
fhash[len[i - 1] + j] = fhash[len[i - 1] + j - 1] * 1313 + buffer[j];
bhash[len[i] - 1 - j] = bhash[len[i] - j] * 1313 + buffer[s - 1 - j];
}
shash[i] = fhash[len[i] - 1];
}
int times;
scanf("%d", &times);
for (int f = 0; f < times; f++) {
int pg, pf, ps;
scanf("%d", &ps);
switch (ps) {
case 1: {
bool bf = false;
scanf("%d", &pf);
for (int i = 1; i < pf; i++) {
if (shash[i] == shash[pf]) {
bf = true;
break;
}
}
printf(bf ? "yes\n" : "no\n");
break;
}
case 2: {
scanf("%d %d", &pg, &pf);
int szv = min(len[pg] - len[pg - 1], len[pf] - len[pf - 1]), i = 0;
for (; i < szv; i++) {
if (fhash[len[pg - 1] + i] != fhash[len[pf - 1] + i])
break;
}
printf("%d\n", i);
break;
}
case 3: {
scanf("%d %d", &pg, &pf);
int szv = min(len[pg] - len[pg - 1], len[pf] - len[pf - 1]), i = 0;
for (; i < szv; i++) {
if (bhash[len[pg] - i - 1] != bhash[len[pf] - i - 1])
break;
}
printf("%d\n", i);
break;
}
}
}
return 0;
}

## zqy2018's solution

/*
Hint: use SAM and hash (or SA?)
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define M 100007ull
using namespace std;
typedef unsigned long long ull;
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct SAM{
int last, D;
int Sigma;
SAM(int sigma){
last = D = 0;
Sigma = sigma;
len[0] = 0, link[0] = -1;
for (int i = 0; i < Sigma; ++i)
to[0][i] = -1;
}
int create_node(){
int res = ++D;
for (int i = 0; i < Sigma; ++i)
to[res][i] = -1;
return res;
}
int copy_node(int src){
int res = ++D;
for (int i = 0; i < Sigma; ++i)
to[res][i] = to[src][i];
return res;
}
inline int get_cid(char c){
return (c == '#' ? 26: c - 'a');
}
void insert(char c){
int cid = get_cid(c);
int cur = create_node();
len[cur] = len[last] + 1;
int p = last;
while (p != -1 && to[p][cid] == -1){
to[p][cid] = cur;
}
if (p == -1){
}else {
int q = to[p][cid];
if (len[p] + 1 == len[q]){
}else {
int clone = copy_node(q);
len[clone] = len[p] + 1;
while (p != -1 && to[p][cid] == q){
to[p][cid] = clone;
}
}
}
last = cur;
}
bool check(const string& s){
int cur = 0, l = s.length();
for (int i = 0; i < l; ++i){
cur = to[cur][get_cid(s[i])];
if (cur == -1) return false;
}
return true;
}
bool check(char* s, int l){
int cur = 0;
for (int i = 0; i < l; ++i){
cur = to[cur][get_cid(s[i])];
if (cur == -1) return false;
}
return true;
}
};
SAM sam(27);
int n;
vector<vector<ull> > hsh_pre, hsh_suf;
bool ans[50005] = {0};
void init(){
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i){
string s;
cin >> s;
ans[i] = sam.check(s);
for (char c: s)
sam.insert(c);
sam.insert('#');

hsh_pre.push_back(vector<ull>());
vector<ull>& v1 = hsh_pre.back();
v1.push_back(0);
ull lst = 0;
for (char c: s)
lst = lst * M + c - 'a',
v1.push_back(lst);

hsh_suf.push_back(vector<ull>());
vector<ull>& v2 = hsh_suf.back();
v2.push_back(0);
lst = 0;
int l = s.length();
for (int i = l - 1; i >= 0; --i)
lst = lst * M + s[i] - 'a',
v2.push_back(lst);
}
}
int lcp(vector<ull>& v1, vector<ull>& v2){
int l = 0, r = max(v1.size(), v2.size());
--r;
while (r > l){
int mid = (l + r + 1) >> 1;
if (v1[mid] == v2[mid])
l = mid;
else r = mid - 1;
}
return l;
}
void solve(){
int q;
cin >> q;
while (q--){
int opr;
cin >> opr;
if (opr == 1){
int t;
cin >> t;
printf("%s\n", (ans[t - 1] ? "yes": "no"));
}
if (opr == 2){
int x, y;
cin >> x >> y;
printf("%d\n", lcp(hsh_pre[x - 1], hsh_pre[y - 1]));
}
if (opr == 3){
int x, y;
cin >> x >> y;
printf("%d\n", lcp(hsh_suf[x - 1], hsh_suf[y - 1]));
}
}
}
int main(){
init();
solve();
return 0;
}