我们有两个集合,A和B.这些集合中的每一个都包括字符串.例如:A - {"abwcd","dwas","www"}和B - {"opqr","tops","ibmd"}我怎样才能计算A组中所有字符串中出现的子序列,但是在B组中没有任何字符串？对于上面的例子,答案是1(子序列"w").
所有这一切都以最佳方式进行.我考虑过使用两次尝试,第一次将所有字符串的所有子序列放在tr中的B中然后,我开始将所有字符串的所有子序列放在trie t_A中的A中,而不更新trie如果相同之前在同一个字符串中找到了子序列(例如:如果我有字符串"aba",我不计算子序列"a"两次).这样,如果我在t_A中找到一个n(大小为A)出现的子序列,我会检查它是否在t_B中,如果不是,我会计算它.但这非常慢,如果A和B的大小为15,字符串长度大约为100个字符,我的程序运行时间超过1秒.
编辑:由于任何子序列在字符串的最后一个字符或在它之前的字符中结束,我们不必生成所有子序列,而是以字符串的最后一个字符结尾的子序列.当我把它们推入trie时,我注意到每个节点都有1.所以如果我有字符串"abcd",我只推"abcd","bcd","cd"和"d",因为这应该是'特里的骨架.但这不是一个非常大的优化,我仍然在寻找更好的东西.
好的,这是交易.我有一堆线性函数,a*x + b.
我的目标是回答以下问题/查询:x = q时的最小函数是什么？
例如:如果我有函数f(x)= 3*x + 2,g(x)= 5*x - 6和h(x)= 2*x + 1,我将回答例如:
对于x = 4,函数h
对于x = 2,函数g
对于x = 1,函数g
我的想法是这样的:
按x的系数按递减顺序对函数进行排序.
按递增顺序对查询进行排序
摆脱并行函数,保留具有最小常数项的函数(例如:如果我有f(x)= 2*x + 4且g(x)= 2*x + 2,则f(x)将永远不会小于g(x),所以我不需要f(x)).
现在我在从-inf到某个实数的区间,称之为w1,我知道在这个区间,线性系数最高的函数是最小的
通过找到最小的x1 st f(x1)= g(x1)找到w1,其中f是我的当前函数,g迭代所有其他具有较小线性系数的函数,w1 = x1
只要我的查询在区间(-inf,w1)中重复:输出当前函数,然后继续下一个查询.
如果我仍然有需要回答的查询,那么让当前函数成为与x = w1处的实际当前函数相交的函数,而不是-inf put w1,重复相同的步骤.
但是,我的实施或想法还不够快.有什么我没注意到可以加速我的程序吗？
先感谢您.
我宣布了一对矢量:
vector <pair <int, int> > args;
然后我想像这样将一对推入向量:
args.push_back((1,-1));
它告诉我逗号的左手操作数没有效果.我哪里出错了？