n个字符串 m个询问 每个询问给出前后缀 并且不重合 问有多少个满足
m挺大 如果在线只能考虑logn的算法
官方题解：对n个串分别存正序倒序 分别按照字典序sort 每一个串就可以被化作一个点 那么对于每一个询问 前后缀都会有一个范围 那就是求这个范围里面的点的个数
官方题解转化到了求矩形并 然而没理解怎么转化 倒是想出来了kdtree直接求范围点 由于前后缀不能重合 即如果有aa aa这个询问 我的办法会找到aaa 就要进行去重
我用map记录 然后每次询问都查询一下。。跑的特别慢。。
但是在写这个博客的时候想出来 可以存三维点 第三维代表这n个串的长度 那么就可以查询len>某个值 进行三维查询
不知道复杂度是不是还会很高。。明天试一下
我的做法：对于n个串 abcde -> abcde*abcde m个询问 ab de -> de*ab 这样直接离线n个串 先把m个询问插进去 记录一下id 直接用n个串跑 最后输出ans
在其中记录fail树上每个点的dep 如果这个点的dep > n个串的长度 就不对答案贡献
但是这样又有了一个新的问题 一模一样的询问会少算 于是我用map<string,int>来记录一下是否已经出现 如果出现了那么这个询问不insert 而是直接指向最早出现的询问
写了一万个bug...不过顺便学习了线段树求矩形面积/周长并
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
#define L long long
#define pb push_back
string a[100050] ;
int n , m ;
char s[500050 * 2] , s2[500050*2];
int ans[100050] ;
struct tire{
int nex[700010*2][27] , fail[700010*2], id[700010*2];
int last[700010*2] ;
int dep[700010*2] ;
int root,l;
int newnode(){
for(int i=0;i<27;i++)nex[l][i]=-1;
last[l]=0;
id[l++]=0;
return l-1;
}
void init(){
l=0;
root=newnode();
dep[root]=0;
}
void inse(string s ,int idd){
int le = s.length() ;
int now=root;
for(int i=0;i<le;i++){
int x;
if(s[i]>=‘a‘&&s[i]<=‘z‘)x=s[i]-‘a‘;
else x=26;
if(nex[now][x] == -1) {
nex[now][x] = newnode();
}
now=nex[now][x];
dep[now]=i+1;
}
id[now]=idd;
}
void build() {
queue<int>q;
fail[root]=root;
for(int i=0;i<27;i++){
if(nex[root][i]==-1)
nex[root][i]=root;
else {
fail[nex[root][i]]=root;
q.push(nex[root][i]);
}
}
while(!q.empty()){
int now=q.front();q.pop();
for(int i= 0;i<27;i++){
if(nex[now][i]==-1)
nex[now][i]=nex[fail[now]][i] ;
else {
fail[nex[now][i]] = nex[fail[now]][i] ;
q.push(nex[now][i]) ;
}
}
}
}
void query(string s, int cd , int num){
int le = s.length() ;
int now=root;
int res = 0 ;
for(int i = 0 ; i < le ; i ++ ) {
int x;
if(s[i]>=‘a‘&&s[i]<=‘z‘)x=s[i]-‘a‘;
else x=26;
now = nex[now][x];
int temp=now;
while(temp!=root){
if(id[temp]!=0 && dep[temp] <= cd+1){
ans[id[temp]]++;
}
temp = fail[temp] ;
}
}
}
}ac;
map<string,int>mp;
int main () {
int t ; scanf("%d",&t);
while(t -- ) {
mp.clear();
ac.init() ;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
cin>>a[i];
}
string c;
memset(ans,0,sizeof(ans));
for(int i=1;i<=m;i++){
string s1,s2;
cin>>s1>>s2;
s2+="*";s2+=s1;
if(mp[s2]!=0)
ans[i]=mp[s2]*-1;
else{
ac.inse(s2,i);
mp[s2]=i;
}
}
ac.build();
for(int i=1;i<=n;i++){
int len=a[i].length() ;
string s=a[i];s+="*";s+=a[i];
ac.query(s , len , i) ;
}
for(int i=1;i<=m;i++){
if(ans[i]<0){
printf("%d\n",ans[ans[i]*(-1)]);
}
else {
printf("%d\n",ans[i]);
}
}
}
}
原文：http://www.cnblogs.com/rayrayrainrain/p/7355569.html