怎么做单页竞价网站wordpress 什么值得买主题

当前位置： 首页 > news >正文

怎么做单页竞价网站,wordpress 什么值得买主题,自助建站好吗,做孵化的网站单模匹配 Brute Force算法#xff08;暴力#xff09; 算法思想 母串和模式串字符依次配对#xff0c;如果配对成功则继续比较后面位置是否相同#xff0c;如果出现匹配不成功的位置#xff0c;则j#xff08;模式串当前的位置#xff09;从头开始#xff0c;i…单模匹配 Brute Force算法暴力 算法思想 母串和模式串字符依次配对如果配对成功则继续比较后面位置是否相同如果出现匹配不成功的位置则j模式串当前的位置从头开始i母串当前的位置回到上一次开始位置的下一个位置。
代码 int brute_force(const char *s, const char *t) {for (int i 0; s[i]; i) {//遍历母串int flag 1;//标志为1说明完成了匹配for (int j 0; t[j]; j) {if (s[i j] t[j]) continue;flag 0;//到达该位置说明出现了失配break;}if (flag 1) return i;}return -1; }Sunday算法 算法思想 和BF的本质区别在于BF的母串每次只往后移动一位Sunday可以移动若干位下面我们讨论若干位具体是多少位。 当前位置失配。 找到模式串最后一位在母串中对应位置后面一个位置黄金对齐点位其值为e同时找到T中最后一次e出现的位置。 移动母串的接下来匹配的开始位置使得上面提到的两个e对其T的j指针从头开始。 新的一轮遍历发现第一个位置就失配。 按照相同的逻辑找到模式串最后一位在母串中对应位置后面一个位置黄金对齐点位其值为a同时找到T中最后一次a出现的位置。 i移动若干位使得两个a能够对齐。 完成匹配。
代码 int sunday(const char *s, const char *t) {int len[256] {0}, n strlen(s), m strlen(t);//len[x]记录当前的黄金对齐点位的元素是x时i需要移动的距离 for (int i 0; i 256; i) len[i] m 1;//默认为m1意思是如果当前值没有在T中出现过那么直接移动m1使得T直接从黄金对齐点位的后面开始匹配 for (int i 0; t[i]; i) len[t[i]] m - i;//移动距离为m-i即T的长度减去所在位置 for (int i 0; i m n; i len[s[i m]]) {int flag 1;//标志为1说明完成了匹配for (int j 0; t[j]; j) {if (s[i j] t[j]) continue;flag 0;//到达该位置说明出现了失配break;}if (flag 1) return i;}return -1; }Boyer Moore 算法 本算法时Sunday算法的前身实现起来比较繁琐复杂。 算法思想 理解 BM 算法的核心法门 失配时模式串尽可能向后移动最大长度移动的长度取决于2条规则中的较大值规则1坏字符规则 delta1规则2好后缀规则 delta2 匹配方向 BM的匹配方向为从后往前。 坏字符规则 向前匹配过程中出现失配点。 此时操作与Sunday类似即移动S指针j使得T最后一次出现v的位置与S中v的位置对齐。 回退bug 但是BM有回退bug在进行上述操作的过程中模式串有可能会往前移显然不可取。 为了解决上面问题引入好后缀规则。 好后缀规则 除了找到最后一次出现的与失配点值相同的位置外坏字符规则也可以找到和已经匹配的序列相同的序列并与S串进行对其。 情况2即无法找到完整的后缀此时蓝色部分后缀一定在T的起始位置证明略。 BM总结
代码 int *getDelta1(const char *t) {int *delta1 (int *)malloc(sizeof(int) * 256);for (int i 0; i 256; i) delta1[i] -1;for (int i 0; t[i]; i) {delta1[t[i]] i;}return delta1; }int *getSuffixes(const char *t) { int tlen strlen(t);int *suff (int *)malloc(sizeof(int) * tlen);suff[tlen - 1] tlen;for (int i 0; i tlen - 1; i) {int j 0;while (j i t[tlen - j - 1] t[i - j]) j;suff[i] j;}return suff; }int *getDelta2(const char *t) {int *suff getSuffixes(t);// printf(suff : );// for (int i 0; t[i]; i) printf(%d , suff[i]);// printf(\n);int tlen strlen(t), lastInd tlen - 1;int *delta2 (int *)malloc(sizeof(int) * tlen);for (int i 0; t[i]; i) delta2[i] tlen;for (int i 0; i tlen; i) {if (suff[i] ! i 1) continue;for (int j 0; j lastInd - suff[i]; j) delta2[j] lastInd - i;}for (int i 0; i lastInd; i) {delta2[lastInd - suff[i]] lastInd - i;}return delta2; }int BM(const char *s, const char *t) {int *delta1 getDelta1(t);int *delta2 getDelta2(t);int slen strlen(s), tlen strlen(t);for (int j 0; j tlen slen;) {int i tlen - 1;while (i 0 t[i] s[j i]) –i;if (i -1) return j;// printf(i%d, delta1[%c]%d, delta2[%d]%d\n, i, s[j i], delta1[s[j i]], i, delta2[i]);j max(i - delta1[s[j i]], delta2[i]);}return -1; }KMP算法 算法思想 出现失配点 将模式串后移使得开始部分能够和S中具有重合 经简单推到得四个蓝色部分相同。 next数组 kmp算法理解的核心与前面三种算法不同的是KMP算法移动的是模式串母串中的位置指针一路向前没有回退。 代码 int *getNext(const char *t) {int tlen strlen(t);int *next (int *)malloc(sizeof(int) * tlen);next[0] -1;//第一个位置特殊处理 int j -1;//含义为当前位置前一个位置得next值 for (int i 1; t[i]; i) {while (j ! -1 t[i] ! t[j 1]) j next[j];//失配找到next[j] if (t[i] t[j 1]) j 1;//成功匹配j1 next[i] j;}return next; }int KMP(const char *s, const char *t) {int *next getNext(t);int j -1, tlen strlen(t);//j为T中当前匹配到的位置 for (int i 0; s[i]; i) {while (j ! -1 s[i] ! t[j 1]) j next[j];//失配模式串移动 if (s[i] t[j 1]) j 1;//成功匹配模式串的位置指针移动 if (t[j 1] 0) return i - tlen 1;//整个T成功匹配返回T在S上开头的位置 }return -1; }完整测试代码 #include iostream #include cstring using namespace std;#define TEST(func, s, t) { \printf(%s(%s, %s) %d\n, #func, s, t, func(s, t));
}int brute_force(const char *s, const char *t) {for (int i 0; s[i]; i) {//遍历母串int flag 1;//标志为1说明完成了匹配for (int j 0; t[j]; j) {if (s[i j] t[j]) continue;flag 0;//到达该位置说明出现了失配break;}if (flag 1) return i;}return -1; }int sunday(const char *s, const char *t) {int len[256] {0}, n strlen(s), m strlen(t);//len[x]记录当前的黄金对齐点位的元素是x时i需要移动的距离 for (int i 0; i 256; i) len[i] m 1;//默认为m1意思是如果当前值没有在T中出现过那么直接移动m1使得T直接从黄金对齐点位的后面开始匹配 for (int i 0; t[i]; i) len[t[i]] m - i;//移动距离为m-i即T的长度减去所在位置 for (int i 0; i m n; i len[s[i m]]) {int flag 1;//标志为1说明完成了匹配for (int j 0; t[j]; j) {if (s[i j] t[j]) continue;flag 0;//到达该位置说明出现了失配break;}if (flag 1) return i;}return -1; }int *getDelta1(const char *t) {int *delta1 (int *)malloc(sizeof(int) * 256);for (int i 0; i 256; i) delta1[i] -1;for (int i 0; t[i]; i) {delta1[t[i]] i;}return delta1; }int *getSuffixes(const char *t) { int tlen strlen(t);int *suff (int *)malloc(sizeof(int) * tlen);suff[tlen - 1] tlen;for (int i 0; i tlen - 1; i) {int j 0;while (j i t[tlen - j - 1] t[i - j]) j;suff[i] j;}return suff; }int *getDelta2(const char *t) {int *suff getSuffixes(t);// printf(suff : );// for (int i 0; t[i]; i) printf(%d , suff[i]);// printf(\n);int tlen strlen(t), lastInd tlen - 1;int *delta2 (int *)malloc(sizeof(int) * tlen);for (int i 0; t[i]; i) delta2[i] tlen;for (int i 0; i tlen; i) {if (suff[i] ! i 1) continue;for (int j 0; j lastInd - suff[i]; j) delta2[j] lastInd - i;}for (int i 0; i lastInd; i) {delta2[lastInd - suff[i]] lastInd - i;}return delta2; }int BM(const char *s, const char *t) {int *delta1 getDelta1(t);int *delta2 getDelta2(t);int slen strlen(s), tlen strlen(t);for (int j 0; j tlen slen;) {int i tlen - 1;while (i 0 t[i] s[j i]) –i;if (i -1) return j;// printf(i%d, delta1[%c]%d, delta2[%d]%d\n, i, s[j i], delta1[s[j i]], i, delta2[i]);j max(i - delta1[s[j i]], delta2[i]);}return -1; }int *getNext(const char *t) {int tlen strlen(t);int *next (int *)malloc(sizeof(int) * tlen);next[0] -1;//第一个位置特殊处理 int j -1;//含义为当前位置前一个位置得next值 for (int i 1; t[i]; i) {while (j ! -1 t[i] ! t[j 1]) j next[j];//失配找到next[j] if (t[i] t[j 1]) j 1;//成功匹配j1 next[i] j;}return next; }int KMP(const char *s, const char *t) {int *next getNext(t);int j -1, tlen strlen(t);//j为T中当前匹配到的位置 for (int i 0; s[i]; i) {while (j ! -1 s[i] ! t[j 1]) j next[j];//失配模式串移动 if (s[i] t[j 1]) j 1;//成功匹配模式串的位置指针移动 if (t[j 1] 0) return i - tlen 1;//整个T成功匹配返回T在S上开头的位置 }return -1; }int main() {char s[100], t[100];while (~scanf(%s%s, s, t)) { TEST(brute_force, s, t);TEST(sunday, s, t);TEST(BM, s, t);TEST(KMP, s, t);}return 0; }多模匹配 Rabin-Karp 基本思想 两种常见的字符串哈希
Rabin_Karp是基于哈希的字符串匹配算法主要基于上面的第二种。 如何在已知hash1的基础上表示出hash2 如果两个字符串具有相同的哈希值要怎么办 一旦匹配到和模式串具有相同哈希值的字符串需要单独进行一次逐个位置的匹配。 代码 单模匹配 #include iostream using namespace std;#define TEST(func, s, t) { \printf(%s(%s, %s) %d\n, #func, s, t, func(s, t));
}#define MOD 9973 #define BASE 131int hash_func(const char *s) {//求取当前模式串的哈希值 int h 0, slen strlen(s);for (int i slen - 1, kbase 1; i 0; i–) {//从后往前越往前权重越大 h (h s[i] * kbase) % MOD;//新找到了一位哈希值更新 kbase kbase * BASE % MOD;//更新权重 }return h; }int RabinKarp(const char *s, const char *t) {int thash hash_func(t);//模式串的哈希值 int nbase 1, tlen;for (tlen 0; t[tlen]; tlen) nbase nbase * BASE % MOD;//为了方便由hashi求出hashj过程中减去开头项引入值nbase for (int i 0, h 0; s[i]; i) {h h * BASE s[i];//更新base if (i tlen) h (h - s[i - tlen] * nbase % MOD MOD) % MOD;//位数足够之后才减去前面的 if (i 1 tlen) continue;//位数不够不执行下面的比较 if (h ! thash) continue; //哈希值不匹配继续下一次 if (strncmp(s i - tlen 1, t, tlen) 0) {//哈希值匹配进行一次逐个位置的检查 return i - tlen 1;//返回当前匹配串的开始位置 }}return -1; }int main() {char s[100], t[100];while (~scanf(%s%s, s, t)) { TEST(RabinKarp, s, t);}return 0; }多模匹配 #include iostream #include string using namespace std;#define MOD 9973 #define BASE 131int hash_func(string s) {//求模式串的哈希值 int h 0;for (int i s.size() - 1, kbase 1; i 0; i–) {h (h s[i] * kbase) % MOD;kbase kbase * BASE % MOD;}return h; }void RabinKarp(string s, vectorstring t) {unordered_mapint, vectorint thash;//存放着哈希值与模式串下标的对应关系 for (int i 0; i t.size(); i) thash[hash_func(t[i])].push_back(i);//遍历每一个模式串求出对应哈希值并存储对应关系 int nbase 1, tlen;for (tlen 0; t[0][tlen]; tlen) nbase nbase * BASE % MOD;for (int i 0, h 0; s[i]; i) {h h * BASE s[i];if (i tlen) h (h - s[i - tlen] * nbase % MOD MOD) % MOD;if (i 1 tlen) continue;if (thash.find(h) thash.end()) continue;//如果当前匹配到串的哈希值没有记录继续向后查找 for (int j 0; j thash[h].size(); j) {//如果查找到了那么就遍历具有当前哈希值的每一个模式串 if (strncmp(s.c_str() i - tlen 1, t[thash[h][j]].c_str(), tlen) 0) {//对于每一个模式串判断时候能够进行匹配 printf(pos %d : %s\n, i - tlen 1, t[thash[h][j]].c_str());}}}return ; }int main() {int n;string s;vectorstring t(100);//存放若干个等待匹配的模式串 cin n;for (int i 0; i n; i) cin t[i];while (cin s) {RabinKarp(s, t);}return 0; }Shift-and 基本思想 将模式串中出现的每一个字符的出现位置进行编码如下图所示1表示在此位置出现。 接下来初始化一个p0每次我们执行如下操作。 如何理解我们每次让p左移一位当前p最左边的位置表示当前能够有机会匹配到的最大长度从最左边1到最右边的距离例如我当前是0100说明上一次我匹配到了两位接下来我要匹配第三位。 只有上一次能够成功匹配我们上一次的1才能左移意味着我要匹配下一位如果我们上一次我们没有成功匹配那么上一次我们得到的结果将会是0因为我们有一个|1的操作意味着我可以得到001此时我将匹配第一位。 匹配完一次之后我们需要判断当前最左边的1是否已经移动了整个字符串的长度。
Shift-and使用的特殊情景 此时可以给以上模式串进行以下编码 a:101 b:101 c:110 d:010 代码 #include iostream using namespace std;#define TEST(func, s, t) { \printf(%s(%s, %s) %d\n, #func, s, t, func(s, t));
}int shift_and(const char *s, const char *t) {int code[256] {0}, n 0;//code表示每一个字符在此规则下的编码 for (n 0; t[n]; n) code[t[n]] | (1 n);//此时的|相当于 int p 0;for (int i 0; s[i]; i) {p (p 1 | 1) code[s[i]];if (p (1 (n - 1))) return i - n 1;}return -1; }int main() {char s[100], t[100];while (~scanf(%s%s, s, t)) {TEST(shift_and, s, t);}return 0; }Shift-or 和Shift-and相比Shift-or只有编码方式的变化。在Shift-or中有效位用0表示此时可以少掉左移以后的或1操作。
字典树 1.Trie字典树 基本思想 图中的节点有红色和白色之分红色表示从根节点到当前位置记录了一个单词。 树的 节点 代表 集合 树的 边 代表 关系 为什么要如此设计 以树形结构的形式进行存储大大减小了查询的开销例如我们要查一个单词hello我们只需要按照以下流程查找查找h如果未查到则直接判断不存在此单词反之查找e如果未查到则直接判断不存在此单词反之查找l以此类推。也就是说我们只是相当于对这个单词遍历了一边时间复杂度相当低。 代码 #include iostream using namespace std;#define BASE 26typedef struct Node {//每个节点存放26个子节点以及一个flag值表示走到当前节点的位置能否表示一个单词 struct Node *next[BASE];int flag; } Node;Node *getNewNode() {//创建一个节点 Node *p (Node *)malloc(sizeof(Node));for (int i 0; i BASE; i) p-next[i] NULL;p-flag 0;return p; }void insert(Node *root, const char *s) {//插入一个单词 Node *p root;//当前检查到的位置 for (int i 0; s[i]; i) {int ind s[i] - a;//当前字符的下标 if (p-next[ind] NULL) p-next[ind] getNewNode();//如果当前位置为空表示这棵树上不存在当前位置的字符此时需要创建 p p-next[ind];//让p走到下一个位置 }p-flag 1;//表示走到当前位置是一个单词 return ; }int find(Node *root, const char *s) {//查找单词 Node *p root;//表示当前检查到的位置 for (int i 0; s[i]; i) {int ind s[i] - a;//当前字符表示的下标 p p-next[ind];//p走到下一个位置 if (p NULL) return 0;//p为空表示匹配到一半时断掉了也即不存在此单词 }return p-flag;//即使每一个字符都成功匹配我们也需要判断最走到后一个节点的路径是否表示了一个完整的单词 }void clear(Node *root) {//递归的方式进行空间释放 if (root NULL) return ;for (int i 0; i BASE; i) clear(root-next[i]);free(root);return ; }void output(Node *root, int k, char *buff) {//按照字典序输出每一个单词 buff[k] 0;//用于下面输出的遍历一但输出到当前位置可以立即停止 if (root-flag) {//找到了单词 printf(find : %s\n, buff);}for (int i 0; i BASE; i) {//每一个子节点 if (root-next[i] NULL) continue;buff[k] i a;//根据下标求出对应的字符 output(root-next[i], k 1, buff);//深搜的方式向下继续查找 }return ; }int main() {int op;char s[100];Node *root getNewNode();do {cin op;if (op 3) break;cin s;switch (op) {case 1: {printf(insert %s to trie\n, s);insert(root, s);} break;case 2: {printf(find %s from trie : %d\n,s, find(root, s));} break;}} while (1);output(root, 0, s);clear(root);return 0; }2.双数组字典树 为什么要有双数组字典树和Trie字典树相比双数组字典树可以大大节省存储空间。 基本思想 双数组字典树使用了两个数组base和check去维护了每一个节点的子节点以及flag值两个关系。 一个节点的子节点序号为basei,其中i为此子节点的字符所对应的编号。例如a对应0这里维护了子节点的关系。但是有一个问题例如两个点的base值分别为89这样的话第一个点走‘c’的孩子和第二个点走‘b’的孩子编号相同显然有问题因此引入了check数组。 check数组的绝对值为当前点父节点的编号同时其正负表示了到达当前点能否形成一个单词负数表示可以正数表示不可以。 本程序的重点问题在于base值的确定。 双数组字典树有一个缺陷——不支持单词的随机插入。再在程中双数组字典树一般和Trie字典树结合使用先将所有的信息插入到Trie字典树中之后再将Trie字典树转化为双数组字典树我们可以再双数组字典树中将base和check数组导出此时我们便可以只拿着这两个数组去做字符串的匹配工作。即离线构造在线查询。 代码 #include iostream using namespace std; #define MAXSIZE 100000 #define BASE 26 typedef struct DANode{//双数组字典树节点定义 int base,check; }DANode; DANode trie[MAXSIZE5]; typedef struct Node {//每个节点存放26个子节点以及一个flag值表示走到当前节点的位置能否表示一个单词 struct Node *next[BASE];int flag; } Node; int da_trie_root1;//根节点的编号 Node *getNewNode() {//创建一个节点 Node *p (Node *)malloc(sizeof(Node));for (int i 0; i BASE; i) p-next[i] NULL;p-flag 0;return p; }void insert(Node *root, const char *s) {//插入一个单词 Node *p root;//当前检查到的位置 for (int i 0; s[i]; i) {int ind s[i] - a;//当前字符的下标 if (p-next[ind] NULL) p-next[ind] getNewNode();//如果当前位置为空表示这棵树上不存在当前位置的字符此时需要创建 p p-next[ind];//让p走到下一个位置 }p-flag 1;//表示走到当前位置是一个单词 return ; }int find(DANode *trie, const char *s) {//查找单词int pda_trie_root; //p为当前节点父节点的编号 for (int i 0; s[i]; i) { int indtrie[p].bases[i]-a;//当前节点的编号 if(abs(trie[ind].check)!p)return 0;//如果当前节点的父节点不是p说明找不到 pind;//更新p }return trie[p].check0;//即使每一个字符都成功匹配我们也需要判断最走到后一个节点的路径是否表示了一个完整的单词 }void clear(Node *root) {//递归的方式进行空间释放 if (root NULL) return ;for (int i 0; i BASE; i) clear(root-next[i]);free(root);return ; } int getbase(Node*root,int ind,DANode*trie)//获取当前节点的base值 {int base2;//从2开始 int flag;do{flag1;for(int i0;iBASE;i){if(!root-next[i])continue;if(!trie[basei].check)continue;//如果当前子节点的check值已存在说明不能取这个位置 base;//更新base flag0;break;}if(flag)break;}while(1);return base; } void convert_to_double_array_trie(Node*root,int ind,DANode*trie)//将trie转化为datrie {trie[ind].basegetbase(root,ind,trie);//获取当前节点的base值 for(int i0;iBASE;i)//对于每一个子节点设置check {if(!root-next[i])continue;trie[trie[ind].basei].check(root-next[i]-flag?-ind:ind); //设置每一个子节点的check值 }for(int i0;iBASE;i)//递归对每一个子节点进行转换 {if(!root-next[i])continue;convert_to_double_array_trie(root-next[i],trie[ind].basei,trie);}return ; } int main() {int n;cinn;char s[100];Node *root getNewNode();for(int i0;in;i){cins;insert(root,s);}convert_to_double_array_trie(root,da_trie_root,trie);while (scanf(%s, s) ! EOF) {printf(find %s from double array trie : %d\n, s, find(trie, s));}clear(root);return 0; }3.可持久化字典树 为什么要引入可持久化字典树或者说可持久化字典树为我们解决了什么特定的问题 普通的字典树只支持在当前插入的所有单词中查找是否存在单词x二可持久化字典树支持在已插入的第i到第j个单词里面查找是否存在x。 基本思想 每插入一个新的单词都创建一个新的根节点故在可持久化字典树里不只有一个根节点。每次创建的新根不仅包含本次插入的单词同时也继承了之前所有能够表示的单词。 初始状态是一个0节点我们插入新的单词abc 接下来插入def我们有两个指针分别指向abc和def的根 把字母d插入 蓝色节点下面是a而绿色节点下面没有a故需要继承从绿色节点引一条边
最终结果因为蓝色节点下面没有d所以def可以一直向下插入 插入abd的最终结果 插入abg的最终结果
代码 #includeiostream using namespace std; #define MAX_N 10000 #define BASE 26 int rt[MAX_N5]{0};//记录每一个根节点的序号 int ch[MAX_N*30][BASE]{0};//记录每一个节点的序号 int val[MAX_N*30]{0};//到达每一个点包含的单词数量 int cnt0;//记录编号递增 void insert(int o,int lst,const char*s)//在o为根节点的树插入s并继承以lst为根的树 {for(int i0;s[i];i)//遍历字符串每一位 {int inds[i]-a;ch[o][ind]cnt;//节点编号赋值 for(int j0;jBASE;j)//对于当前节点每一条边 {if(ch[o][j])continue;//只会出现一次即在上方赋值过 ch[o][j]ch[lst][j];//未出现则赋值为lst节点以j为边的下一个节点的序号 }och[o][ind];//更新o为o以ind为边的下一个节点 lstch[lst][ind];val[o]val[lst];//将lst为节点的val值拷贝给o节点 }val[o]1;return ; } int find_once(int a,const char*s)//在a中查s出现的数量 {int prt[a];//p记录当前编号 for(int i0;s[i];i){pch[p][s[i]-a];}return val[p]; } int query(int a,int b,const chars)//作差查询ab区间是否出现s {int x1find_once(b,s);int x2find_once(a-1,s);return x1-x2; } int main() {int n;cinn;char s[100];for(int i1;in;i){cins;rt[i]cnt;//根节点编号赋值 insert(rt[i],rt[i-1],s); }int a,b;while (~scanf(%d%d%s, a, b, s)) {printf(from %d to %d, find %s : %d\n,a, b, s, query(a, b, s));}return 0; }AC自动机 基本思想 AC自动机是结合了KMP算法的思想以字典树为基础实现的。 在KMP中对于模式串每个位置都记录了最大匹配长度这样可以在失配的时候直接据此对模式串进行一个大距离的移动而不需要逐一匹配。在若干个单词构成的字典树里如果我们想知道在一个模式串中这些单词出现的有哪些我们同样可以在失配的时候直接转向当前位置对应的下一位置而不需要从头重新进行匹配。 每一个节点都有一个fail指针指向在此位置失配后要转向的位置。
代码 /************************************************************************ File Name: 11.ac.cpp Author: hug Mail: hughaizeix.com Created Time: 浜? ³⁄₂₆ 21:10:59 2024**********************************************************************/#include iostream #include queue using namespace std;#define BASE 26typedef struct Node {int flag;struct Node *next[26];struct Node *fail;//失败指针 const char *s;//记录当前点所表示的单词便于直接输出 } Node;Node *getNewNode() {//初始化一个节点 Node *p (Node *)malloc(sizeof(Node));p-flag 0;p-fail NULL;p-s NULL;for (int i 0; i BASE; i) p-next[i] NULL;return p; }void insert(Node *root, const char *s) {//插入一个单词 Node *p root;//p指向当前位置 for (int i 0; s[i]; i) {//遍历单词的每一位 int ind s[i] - a;//当前单词对应的下标 if (p-next[ind] NULL) p-next[ind] getNewNode();//如果当前字符不存在字典树中创建一个新的节点 p p-next[ind];//p往后走一个走到当前位置 }p-s strdup(s);//当前位置是一个单词的末尾把s赋值给p-s p-flag 1;return ; }void build_ac(Node *root) {//建立ac自动机以层序遍历的方式 queueNode * q;for (int i 0; i BASE; i) {//对于根节点 if (root-next[i] NULL) continue;root-next[i]-fail root;//对于根节点的下面一层节点失败指针可以直接连接到根节点 q.push(root-next[i]);//进入队列 }while (!q.empty()) {//不断从队列取出Node Node *cur q.front(), *p;q.pop();for (int i 0; i BASE; i) {//对于每一个cur确定他每一个孩子节点的fail if (cur-next[i] NULL) continue;p cur-fail;//p指向cur的fail while (p p-next[i] NULL) p p-fail;//如果p后面不能接ia则继续向上寻找p一直到NULL为止 if (p NULL) p root;else p p-next[i];cur-next[i]-fail p;q.push(cur-next[i]);}}return ; }void find_ac(Node *root, const char *s) {//寻找ac自动机中在s中出现的所有单词 Node *p root, *q;//p指向当前节点 for (int i 0; s[i]; i) {int ind s[i] - a;while (p p-next[ind] NULL) p p-fail;//如果当前节点下无法找到该字符则不断向上走 if (p NULL) p root;else p p-next[ind];q p;while (q) {//为什么要while如果s中包含worldac自动机中又包含worldrldld那么while才可以保证输出每一个存在的单词 if (q-flag) {int len strlen(q-s);printf(find [%d, %d] %s\n, i - len 1, i, q-s);}q q-fail;}}return ; }void clear(Node *root) { if (root NULL) return ;for (int i 0; i BASE; i) {if (root-next[i] NULL) continue;clear(root-next[i]);}free(root);return ; }int main() {int n;char s[100];Node *root getNewNode();scanf(%d, n);for (int i 0; i n; i) {scanf(%s, s);insert(root, s);}build_ac(root);scanf(%s, s);find_ac(root, s);return 0; }线索化优化 借鉴线索二叉树的思想这里要充分利用空指针。如果一个节点cur的next[i]为NULL那么让他指向cur-fail-next[i]。
代码 /*********************************************************************** File Name: 11.ac.cpp Author: hug Mail: hughaizeix.com Created Time: 浜? ³⁄₂₆ 21:10:59 2024************************************************************************/#include iostream #include queue using namespace std;#define BASE 26typedef struct Node {int flag;struct Node *next[26];struct Node *fail;const char *s; } Node;vectorNode * node_vec;Node *getNewNode() {Node *p (Node *)malloc(sizeof(Node));p-flag 0;p-fail NULL;p-s NULL;for (int i 0; i BASE; i) p-next[i] NULL;node_vec.push_back(p);return p; }void insert(Node *root, const char *s) {Node *p root;for (int i 0; s[i]; i) {int ind s[i] - a;if (p-next[ind] NULL) p-next[ind] getNewNode();p p-next[ind];}p-s strdup(s);p-flag 1;return ; }void build_ac(Node *root) {queueNode * q;q.push(root);while (!q.empty()) {Node *cur q.front(), *p;q.pop();for (int i 0; i BASE; i) {if (cur-next[i] NULL) {if (cur root) cur-next[i] root;else cur-next[i] cur-fail-next[i];continue;}p cur-fail;if (p NULL) p root;else p p-next[i];cur-next[i]-fail p;q.push(cur-next[i]);}}return ; }void find_ac(Node *root, const char *s) {Node *p root, *q;for (int i 0; s[i]; i) {int ind s[i] - a;p p-next[ind];q p;while (q) {if (q-flag) {int len strlen(q-s);printf(find [%d, %d] %s\n, i - len 1, i, q-s);}q q-fail;}}return ; }void clear() {for (int i 0; i node_vec.size(); i) {free(node_vec[i]);}return ; }int main() {int n;char s[100];Node *root getNewNode();scanf(%d, n);for (int i 0; i n; i) {scanf(%s, s);insert(root, s);}build_ac(root);scanf(%s, s);find_ac(root, s);clear();return 0; }练习题 AC自动机模板题 ⁸⁄₁₀₀ 发布文章 m0_70897036 未选择文件 AC 自动机简单版 题目描述 给定 n n n 个模式串 s i s_i si​ 和一个文本串 t t t求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们编号不同。 输入格式 第一行是一个整数表示模式串的个数 n n n。 第 2 2 2 到第 ( n 1 ) (n 1) (n1) 行每行一个字符串第 ( i 1 ) (i 1) (i1) 行的字符串表示编号为 i i i 的模式串 s i s_i si​。 最后一行是一个字符串表示文本串 t t t。 输出格式 输出一行一个整数表示答案。 样例 #1 样例输入 #1 3 a aa aa aaa样例输出 #1 3样例 #2 样例输入 #2 4 a ab ac abc abcd样例输出 #2 3样例 #3 样例输入 #3 2 a aa aa样例输出 #3 2提示 样例 1 解释 s 2 s_2 s2​ 与 s 3 s_3 s3​ 编号下标不同因此各自对答案产生了一次贡献。 样例 2 解释 s 1 s_1 s1​ s 2 s_2 s2​ s 4 s4 s4​ 都在串 abcd 里出现过。 数据规模与约定 对于 50 % 50\% 50% 的数据保证 n 1 n 1 n1。对于 100 % 100\% 100% 的数据保证 1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^6 1≤n≤106 1 ≤ ∣ t ∣ ≤ 1 0 6 1 \leq |t| \leq 10^6 1≤∣t∣≤106 1 ≤ ∑ i 1 n ∣ s i ∣ ≤ 1 0 6 1 \leq \sum\limits{i 1}^n |s_i| \leq 10^6 1≤i1∑n​∣si​∣≤106。 s i , t s_i, t si​,t 中仅包含小写字母。 代码实现 #includeiostream using namespace std; #define MAXSIZE 1000000 int node[MAXSIZE5][26]; int fail[MAXSIZE5]{0}; int val[MAXSIZE5]{0}; int que[MAXSIZE5]{0}; char s[MAXSIZE5]; int cnt1,root1; int getNewNode() {return cnt; } void insert(const char*s) {int proot;for(int i0;s[i];i){int inds[i]-a;if(!node[p][ind])node[p][ind]getNewNode();pnode[p][ind];}val[p]1;return ; } void build_ac() {int head0,tail0,p;que[tail]root;while(headtail){int curque[head];for(int i0;i26;i){if(!node[cur][i]){if(!fail[cur])node[cur][i]root;else node[cur][i]node[fail[cur]][i];continue;}pfail[cur];if(p0)proot;else pnode[p][i];fail[node[cur][i]]p;que[tail]node[cur][i];} }return ; } int find_all(const char*s) {int proot,q,ans0;for(int i0;s[i];i){int inds[i]-a;pnode[p][ind];qp;while(qval[q]!-1){ansval[q];val[q]-1;qfail[q];}}return ans; } int main() {int n;cinn;for(int i0;in;i){scanf(%s\n,s);insert(s);}build_ac();scanf(%s,s);coutfind_all(s);return 0;} AC 自动机简单版 II 题目描述 有 N N N 个由小写字母组成的模式串以及一个文本串 T T T。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 T T T 中出现的次数最多。 输入格式 输入含多组数据。保证输入数据不超过 50 50 50 组。 每组数据的第一行为一个正整数 N N N表示共有 N N N 个模式串 1 ≤ N ≤ 150 1 \leq N \leq 150 1≤N≤150。 接下去 N N N 行每行一个长度小于等于 70 70 70 的模式串。下一行是一个长度小于等于 1 0 6 10^6 106 的文本串 T T T。保证不存在两个相同的模式串。 输入结束标志为 N 0 N0 N0。 输出格式 对于每组数据第一行输出模式串最多出现的次数接下去若干行每行输出一个出现次数最多的模式串按输入顺序排列。 样例 #1 样例输入 #1 2 aba bab ababababac 6 beta alpha haha delta dede tata dedeltalphahahahototatalpha 0样例输出 #1 4 aba 2 alpha haha代码实现 #includeiostream #includequeue #includecstring using namespace std; typedef struct Node{int id;Node*fail;Node*next[26]; }Node; int node_cnt0; char s[1000005],t[200][75]; int tcnt[200]; Node*getNewNode() {Nodep(Node)malloc(sizeof(Node));p-id-1;p-failNULL;for(int i0;i26;i)p-next[i]NULL;return p; } void insert(Node*root,const char*s,int k) {Node*proot;for(int i0;s[i];i){int inds[i]-a;if(!p-next[ind])p-next[ind]getNewNode();pp-next[ind];}p-idk;strcpy(t[k],s);return ; } void build_ac(Node*root) {queueNode*q;q.push(root);while(!q.empty()){Node*curq.front();q.pop();for(int i0;i26;i){if(!cur-next[i]){if(!cur-fail)cur-next[i]root;else cur-next[i]cur-fail-next[i];continue;} Node*pcur-fail;if(!p)proot;else pp-next[i];cur-next[i]-failp;q.push(cur-next[i]);}}return ; } void find_ac(Node*root,const char*s) {Node*proot,*q;for(int i0;s[i];i){int inds[i]-a;pp-next[ind];qp;while(q){if(q-id!-1)tcnt[q-id];qq-fail;}}return ; } void Init() {node_cnt0;memset(t,0,sizeof(t));memset(tcnt,0,sizeof(tcnt));return ; } void solve(int n) {Init();Node*rootgetNewNode();for(int i0;in;i){scanf(%s,s);insert(root,s,i);}build_ac(root);scanf(%s,s);find_ac(root,s);int ans0;for(int i0;in;i){if(anstcnt[i])anstcnt[i];}printf(%d\n,ans);for(int i0;in;i){if(anstcnt[i])printf(%s\n,t[i]);}return ; } int main() {int n;while(~scanf(%d,n)!EOF){if(n0)break;solve(n);}return 0;} 循环的字符串 题目描述 ​ 给出一个字符串从字符串起始位遍历到最后一位若起始位至当前位能被一个前缀串循环 n 次组成则输出当前位的位置和 n。n≥2 输入 ​ 第一行输入一个数 L 表示字符串长度。 ​ 第二行输入字符串。 输出 ​ 每当能达成题目要求时输出一行两个数表示当前位置和 n。 样例输入 12 aabaabaabaab 样例输出 2 2 6 2 9 3 12 4 解题思路 下面需要证明一个结论当字符串的2-6于1-5部分重合时如果字符串长度n是1部分的长度m的整数倍时1部分是字符串的循环节。 因为上下是同一个字符串所以上1下1上2下2又上2下1所以黄色四部分相等。 因为上3下3上3下2所以黄色六个部分相等。 同理如果n为m的整数倍则每一个m长度的部分均相等。
代码实现 #includeiostream using namespace std; #define MAX_N 1000000 int nxt[MAX_N5]; char s[MAX_N5]; void get_nxt()//参考KMPnext数组的求解 {int j-1;nxt[0]-1;for(int i1;s[i];i){while(j!-1s[j1]!s[i])jnxt[j];if(s[j1]s[i])j1; nxt[i]j;}return ; } int main() {int n;cinn;cins;get_nxt();for(int i1;in;i)//从字符串第二位开始{int ni1,mn-nxt[i]-1;//n表示当前字符串的长度:下标1n的值为字符串长度减去重叠部分长度即nxt[i]1if(n%m0n/m2)//如果n是m整数倍同时存在相交的部分{printf(%d %d\n,n,n/m);}}return 0;} 项链的主人 题目描述 ​ 有一天小明同学捡到了一条价值连城宝石项链他想知道项链的主人是谁。在得知此事后很多人向小明发来了很多邮件都说项链是自己的要求他归还显然其中最多只有一个人说了真话。 ​ 小明要求每个人都写了一段关于自己项链的描述 ​ 项链上的宝石用数字 0 至 9 来表示。一个对于项链的表示就是从项链的某个宝石开始逆时针绕一圈沿途记下经过的宝石比如如下项链
​ 它的可能的四种表示是 0123,1230,2301,3012。 ​ 给定两个项链的表示判断他们是否可能是一条项链。注意项链是不会翻转的。 输入 ​ 输入文件只有两行每行一个由 0 至 9 组成的字符串描述一个项链的表示保证项链的长度是相等的。 输出 ​ 如果两条项链不可能同构那么输出 No否则的话第一行输出一个 Yes第二行输出该项链的字典序最小的表示。L 为项链长度。 样例输入 2234342423 2423223434 样例输出 Yes 2234342423 解题思路 求出两个项链的字典序最小的表示之后逐个位置比较。 循环这个过程。 代码实现 #includeiostream #includecstring using namespace std; #define MAX_N 1000000 char s[MAX_N5],t[MAX_N5]; int string_min(char*s) {int nstrlen(s);int i0,j1,k0;while(injnkn){if(s[(ik)%n]s[(jk)%n])k1;else if(s[(ik)%n]s[(jk)%n]){iki1;k0;}else {jkj1;k0;}if(ij)i1;}return min(i,j); } int main() {scanf(%s,s);scanf(%s,t);int szstrlen(s);int min_sstring_min(s),min_tstring_min(t);int flag1;for(int imin_s,jmin_t,n0;nsz;n){if(s[(in)%sz]t[(jn)%sz])continue;flag0;break;}if(flag){coutYesendl;for(int imin_s,n0;nsz;n)printf(%c,s[(in)%sz]);coutendl;}else{coutNoendl;}return 0;} 前缀统计 题目描述 ​ 给定 N 个字符串 S1,S2…SN接下来进行 M 次询问每次询问给定一个字符串 T求 S1−SN中有多少个字符串是 T 的前缀。输入字符串的总长度不超过 106仅包含小写字母。 输入 ​ 第一行两个整数 N,M。接下来 N 行每行一个字符串 Si。接下来 M 行每行一个字符串表示询问。 输出 ​ 对于每个询问输出一个整数表示答案。 样例输入 3 2 ab bc abc abc efg 样例输出 2 0 解题思路 套用字典树模板将前n组数插入到字典树中之后在字典树中分别查找后m的字符串如果某个字符串路径上有完整单词存在则cnt。 代码实现 #includeiostream #includestdlib.h #includecstring using namespace std; #define MAX_N 1000000 #define BASE 26 typedef struct Node{struct Node*next[BASE];int flag;int val; }Node; char s[MAX_N5],t[MAX_N5]; Node*getNewNode() {Nodep(Node)malloc(sizeof(Node));for(int i0;iBASE;i)p-next[i]NULL;p-flag0;p-val0;return p; } void insert(Node*root,char*s) {Node*proot;for(int i0;s[i];i){int inds[i]-a;if(!p-next[ind])p-next[ind]getNewNode();pp-next[ind];}p-val;p-flag1;return ; } int query(Node*root,char*s) {int cnt0;Node*proot;for(int i0;s[i];i){int inds[i]-a;if(!p-next[ind])break;if(p-next[ind]-flag)cntp-next[ind]-val;pp-next[ind];}return cnt; } int main() {int n,m;cinnm;Node*rootgetNewNode();while(n–){scanf(%s,s);insert(root,s);}while(m–){scanf(%s,t);printf(%d\n,query(root,t));}return 0; }最大异或对 题目描述 ​ 在给定的 N 个正整数 A1A2……AN 中选出两个进行异或运算得到的结果最大是多少 输入 ​ 第一行一个整数 N第二行 N 个正整数 A1−AN。 输出 ​ 输出一个整数表示答案。 样例输入 3 1 2 3 样例输出 3 解题思路 首先把每一个对应的二进制数存放到字典树中之后分别在字典树中遍历每一个数求出其最大的异或值求解逻辑为尽可能选择和当前位不一样的值若当前位是0则选择1如果不存在则只能选择相同的值最后在所有异或值里面选择最大的。 代码实现 #includeiostream #includestdlib.h using namespace std; #define MAX_N 100000 #define BASE 31 int s[MAX_N5]; typedef struct Node{struct Node*next[2];int val; }Node; Node*getNewNode() {Nodep(Node)malloc(sizeof(Node));p-next[0]NULL;p-next[1]NULL;p-val0;return p; } void insert(Node*root,int a) {Node*proot;for(int iBASE;i0;i–){if(a/(1i)1){a-(1i); if(!p-next[1])p-next[1]getNewNode();pp-next[1]; }else{if(!p-next[0])p-next[0]getNewNode();pp-next[0]; } }p-val1;return ; } int query(Node*root,int a) {int ans0;Node*proot;for(int iBASE;i0;i–){if(a/(1i)1){a-(1i); if(!p-next[0])pp-next[1];else{pp-next[0];ans(1i);} }else{if(!p-next[1])pp-next[0];else{pp-next[1];ans(1i);} } }return ans; } int main() {int n;cinn;Node*rootgetNewNode();for(int i0;in;i){scanf(%d,s[i]);insert(root,s[i]);}int max_val0;for(int i0;in;i){max_valmax(max_val,query(root,s[i]));}coutmax_val;return 0;} 拨号 题目描述 观察如下的电话号码组 ​ 911,91152358 有一部奇怪的电话机若想拨打 91152358 这个号码当输入前缀 911 时由于 911 这个号码的存在会直接拨通 911 这个号码导致无法拨通 91152358。现在给定 N 个号码判断所有号码是否都能拨通。 输入 ​ 第一行一个整数 N接下来 N 行每行一个电话号。 输出 ​ 每个号码都能拨通输出 YES否则输出 NO。 样例输入 5 113 12340 123440 12345 98346 样例输出 YES 解题思路 把每一个号码插入到字典树中之后分别在字典树中遍历每一个号码如果在此号码的路径上存在一个完整的号码则输出NO。 代码实现 #includeiostream #includestdlib.h using namespace std; #define MAX_N 10000 #define BASE 10 char s[MAX_N5][MAX_N5]; typedef struct Node{Node*next[BASE];int flag; }Node; Node*getNewNode() {Nodep(Node)malloc(sizeof(Node));for(int i0;iBASE;i)p-next[i]NULL;p-flag0;return p; } void insert(Node*root,char*t) {Node*proot;for(int i0;t[i];i){int indt[i]-0;if(!p-next[ind])p-next[ind]getNewNode();pp-next[ind];}p-flag1;return ; } bool query(Node*root,char*t) {Node*proot;for(int i0;t[i];i){int indt[i]-0;if(p-flag)return 0;pp-next[ind];}return 1; } int main() {int n;cinn;Node*rootgetNewNode();for(int i0;in;i){scanf(%s,s[i]);insert(root,s[i]);}for(int i0;in;i){if(!query(root,s[i])){coutNOendl;return 0;}}coutYESendl;return 0; }【模板】字符串哈希 题目描述 如题给定 N N N 个字符串第 i i i 个字符串长度为 M i M_i Mi​字符串内包含数字、大小写字母大小写敏感请求出 N N N 个字符串中共有多少个不同的字符串。 友情提醒如果真的想好好练习哈希的话请自觉。 输入格式 第一行包含一个整数 N N N为字符串的个数。 接下来 N N N 行每行包含一个字符串为所提供的字符串。 输出格式 输出包含一行包含一个整数为不同的字符串个数。 样例 #1 样例输入 #1 5 abc aaaa abc abcc 12345样例输出 #1 4提示 对于 30 % 30\% 30% 的数据 N ≤ 10 N\leq 10 N≤10 M i ≈ 6 M_i≈6 Mi​≈6 M m a x ≤ 15 Mmax\leq 15 Mmax≤15。 对于 70 % 70\% 70% 的数据 N ≤ 1000 N\leq 1000 N≤1000 M i ≈ 100 M_i≈100 Mi​≈100 M m a x ≤ 150 Mmax\leq 150 Mmax≤150。 对于 100 % 100\% 100% 的数据 N ≤ 10000 N\leq 10000 N≤10000 M i ≈ 1000 Mi≈1000 Mi​≈1000 M m a x ≤ 1500 Mmax\leq 1500 Mmax≤1500。 样例说明 样例中第一个字符串(abc)和第三个字符串(abc)是一样的所以所提供字符串的集合为{aaaa,abc,abcc,12345}故共计4个不同的字符串。 Tip 感兴趣的话你们可以先看一看以下三题 BZOJ3097http://www.lydsy.com/JudgeOnline/problem.php?id3097 BZOJ3098http://www.lydsy.com/JudgeOnline/problem.php?id3098 BZOJ3099http://www.lydsy.com/JudgeOnline/problem.php?id3099 如果你仔细研究过了或者至少仔细看过AC人数的话我想你一定会明白字符串哈希的正确姿势的 代码实现 #includeiostream #includeunordered_map #includevector #includestring using namespace std; long long get_hash(string s) {long long base131,num0;for(int i0;is.size();i){num((num*base)%20030524s[i])%20030524;}return num; } char s[1500]; int main() {int n;cinn;int cnt0;long long hash_code;unordered_maplong long,vectorstringh;for(int i0;in;i){scanf(%s,s);hash_codeget_hash(s);if(h.find(hash_code)h.end()){cnt;h[hash_code].push_back(s);}else{int flag1;for(auto j:h[hash_code]){if(s!j)continue;flag0;break;}if(flag){cnt;h[hash_code].push_back(s);}}}coutcnt;return 0; }[USACO2.3] 最长前缀 Longest Prefix 题目描述 在生物学中一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列即元素很感兴趣。 如果一个集合 P P P 中的元素可以串起来元素可以重复使用组成一个序列 s s s 那么我们认为序列 s s s 可以分解为 P P P 中的元素。元素不一定要全部出现如下例中 BBC 就没有出现。举个例子序列 ABABACABAAB 可以分解为下面集合中的元素{A,AB,BA,CA,BBC} 序列 s s s 的前面 k k k 个字符称作 s s s 中长度为 k k k 的前缀。设计一个程序输入一个元素集合以及一个大写字母序列 设 s ′ s s′ 是序列 s s s 的最长前缀使其可以分解为给出的集合 P P P 中的元素求 s ′ s s′ 的长度 k k k。 输入格式 输入数据的开头包括若干个元素组成的集合 O O O用连续的以空格分开的字符串表示。字母全部是大写数据可能不止一行。元素集合结束的标志是一个只包含一个 . 的行集合中的元素没有重复。 接着是大写字母序列 s s s 长度为用一行或者多行的字符串来表示每行不超过 76 76 76 个字符。换行符并不是序列 s s s 的一部分。 输出格式 只有一行输出一个整数表示 S 符合条件的前缀的最大长度。 样例 #1 样例输入 #1 A AB BA CA BBC . ABABACABAABC样例输出 #1 11提示 【数据范围】 对于 100 % 100\% 100% 的数据 1 ≤ card ( P ) ≤ 200 1\le \text{card}(P) \le 200 1≤card(P)≤200 1 ≤ ∣ S ∣ ≤ 2 × 1 0 5 1\le |S| \le 2\times 10^5 1≤∣S∣≤2×105 P P P 中的元素长度均不超过 10 10 10。 翻译来自NOCOW USACO 2.3 解题思路 把集合中的元素加入到字典树中对字符串进行一次遍历如果以当前位开头不存在一个完整的单词则跳过该位否则寻找以当前位开头能匹配到的所有单词并记录在字符串中对应的最后一位以便下一次允许从此位置往后寻找被记录的最大值就是答案。 代码实现 #includeiostream #includestring using namespace std; #define BASE 26 #define MAX_N 200000 int dp[MAX_N5]; typedef struct Node{Node*next[BASE];int val;int dep; }Node; Node*getNewNode() {Nodep(Node)malloc(sizeof(Node));for(int i0;iBASE;i)p-next[i]NULL;p-val0;p-dep0;return p; } void insert(Node*root,string s) {Node*proot;for(int i0;s[i];i){int inds[i]-A;if(!p-next[ind])p-next[ind]getNewNode();p-next[ind]-depp-dep1;pp-next[ind];}p-val1;return ; } void mark(Node*root,string s,int pos) {Node*proot;for(int ipos;s[i];i){int inds[i]-A;if(!p-next[ind])return ;pp-next[ind];if(p-val)dp[posp-dep]1;}return ; } int main() {string s,t;Node*rootgetNewNode();while(cins){if(s.)break;insert(root,s);}s;while(cint)st;dp[0]1;int ans0;for(int i0;s[i];i){if(dp[i]0)continue;ansi;mark(root,s,i);}if(dp[s.size()])anss.size();coutans;return 0; } 【模板】字典树 题目描述 给定 n n n 个模式串 s 1 , s 2 , … , s n s_1, s_2, \dots, s_n s1​,s2​,…,sn​ 和 q q q 次询问每次询问给定一个文本串 t i t_i ti​请回答 s 1 ∼ s n s_1 \sim s_n s1​∼sn​ 中有多少个字符串 s j s_j sj​ 满足 t i t_i ti​ 是 s j s_j sj​ 的前缀。 一个字符串 t t t 是 s s s 的前缀当且仅当从 s s s 的末尾删去若干个可以为 0 个连续的字符后与 t t t 相同。 输入的字符串大小敏感。例如字符串 Fusu 和字符串 fusu 不同。 输入格式 本题单测试点内有多组测试数据。 输入的第一行是一个整数表示数据组数 T T T。 对于每组数据格式如下 第一行是两个整数分别表示模式串的个数 n n n 和询问的个数 q q q。 接下来 n n n 行每行一个字符串表示一个模式串。 接下来 q q q 行每行一个字符串表示一次询问。 输出格式 按照输入的顺序依次输出各测试数据的答案。 对于每次询问输出一行一个整数表示答案。 样例 #1 样例输入 #1 3 3 3 fusufusu fusu anguei fusu anguei kkksc 5 2 fusu Fusu AFakeFusu afakefusu fusuisnotfake Fusu fusu 1 1 998244353 9样例输出 #1 2 1 0 1 2 1提示 数据规模与约定 对于全部的测试点保证 1 ≤ T , n , q ≤ 1 0 5 1 \leq T, n, q\leq 10^5 1≤T,n,q≤105且输入字符串的总长度不超过 3 × 1 0 6 3 \times 10^6 3×106。输入的字符串只含大小写字母和数字且不含空串。 说明 std 的 IO 使用的是关闭同步后的 cin/cout本题不卡常。 解题思路 在插入的时候每路过一个节点就让该节点的cnt表示以从根节点到此节点为前缀的字符串的数量1之后询问的字符串的最后一个节点的cnt值就是以此字符串为前缀的字符串数量。 代码实现 #includeiostream using namespace std; #define MAX_N 100000 #define MAX_LEN 3000000 #define BASE 62 char s[MAX_LEN5]; typedef struct Node{Node*next[BASE];int flag;int val; int cnt; }Node; Node*getNewNode() {Nodep(Node)malloc(sizeof(Node));for(int i0;iBASE;i)p-next[i]NULL;p-val0;p-cnt0;p-flag0;return p; } void insert(Node*root,char*s) {Node*proot;for(int i0;s[i];i){p-cnt1;int ind;if(s[i]a)inds[i]-a36;else if(s[i]A)inds[i]-A10;else inds[i]-0;if(!p-next[ind])p-next[ind]getNewNode();pp-next[ind];}p-cnt1;p-val1;p-flag1;return ; } int query(Node*root,char*s) {Node*proot;for(int i0;s[i];i){int ind;if(s[i]a)inds[i]-a36;else if(s[i]A)inds[i]-A10;else inds[i]-0;if(!p-next[ind])return 0;pp-next[ind];}return p-cnt; } void clear(Node*root) {if(!root)return ;for(int i0;iBASE;i)if(!root-next[i])clear(root-next[i]);free(root);return ; } int main() {int t,a,b;cint;while(t–){Node*rootgetNewNode();scanf(%d%d,a,b);while(a–){scanf(%s,s);insert(root,s);}while(b–){cins;coutquery(root,s)endl;}clear(root);}return 0; }