题目： http://poj.org/problem?id=2001 题意： 找到多个字符串中，各自唯一的最短子串，例如 carte 与 carce 各自唯一的最短子串为cart与carc，即不会与其它字符串的子串重复。 思路: 字典树 解题心得: 更新关键值的时机很重要 代码： #include<stdio.h>#include<string>typedef str

题意：求一个字符串有后缀与前缀相同的前缀在串中出现的次数。 分析：根据next数组可求出所有前缀在传中出现的次数，dp[next[i]]+=dp[i]，dp[i]初始为1。也可以很简单得求出哪些前缀有相同的后缀。 #include<iostream>#include<string>#include<cstring>#include<cstdio>#include<cmath>#i

The length of the longest common prefix of two strings 𝑠=𝑠1𝑠2…𝑠𝑛 and 𝑡=𝑡1𝑡2…𝑡𝑚 is defined as the maximum integer 𝑘 (0≤𝑘≤𝑚𝑖𝑛(𝑛,𝑚)) such that 𝑠1𝑠2…𝑠𝑘 equals 𝑡1𝑡2…𝑡𝑘. Koa the Ko

D. Prefixes and Suffixes time limit per test 1:second memory limit per test: 256 megabytes input: standard input output: standard output You have a string s = s1s2...s|s|, wh

Description GAL发现了N个特殊的字母序列，由小写字母组成。小L认为，对于两个字符串s1,s2，若s1是某个特殊序列的前缀，s2是该特殊序列的后缀，则称s1,s2被这个序列拥有。 现在小L给出M对s1,s2，对于每对字符串，问它们被几个特殊序列拥有。 Input  第1行一个整数N。 接下来N行，每行一个字符串，代表N个特殊序列。 第N+2行一个整数M。 接下来M行每行一

题目链接：http://poj.org/problem?id=2001 题意：给出若干字符串，求每一个字符串的最短唯一表示前缀 题解： 一看这种找前缀的东西肯定是trie 插入的时候每路过一个点，cnt++ 查询的时候走到第一个cnt=1即可，如果没有，就输出这个串 #include<iostream>#include<cstdio>#include<cstring>#inclu