在过去的几周里,我试图弄清楚如何在另一个字符串中有效地找到字符串模式.
我发现很长一段时间,最有效的方法是使用后缀树.但是,由于这种数据结构在空间上非常昂贵,我进一步研究了后缀数组的使用(使用的空间要少得多).不同的论文,如"后缀数组:一种新的在线字符串搜索方法"(Manber&Myers,1993)指出,搜索子字符串可以在O(P + log(N))中实现(其中P是通过使用二进制搜索和后缀数组以及LCP数组,模式的长度和N是字符串的长度.
我特别研究了后一篇论文来理解搜索算法.这个答案在帮助我理解算法方面做得非常出色(并顺便将其纳入LCP维基百科页面).
但我仍在寻找实现此算法的方法.特别是所提到的LCP-LR阵列的构造看起来非常复杂.
参考文献:
Manber&Myers,1993:Manber,Udi; Myers,Gene,SIAM Journal on Computing,1993,Vol.22(5),pp.935-948,http: //epubs.siam.org/doi/pdf/10.1137/0222058
更新1
只是为了强调我感兴趣的东西:我理解LCP数组,并找到了实现它们的方法.但是,"普通"LCP阵列不适合有效的模式匹配(如参考文献中所述).因此,我对实现LCP-LR阵列感兴趣,这似乎比实现LCP阵列复杂得多
更新2
添加了参考文件的链接
这段代码:
QString output("test1\ntest2");
qDebug() << output;
导致这个输出:
"test1\ntest2"
我想要的是:
"test1
test2"
那么我如何使用qDebug()(和类似的输出函子)来打印包含多行换行符的QString？
我正在维护一个autoconf软件包,并希望集成自动测试.我使用Boost Unit Test Framework我的单元测试,并能够成功地将其集成到包中.
也就是说它可以通过编译make check,但是没有运行(尽管我读过它们make check都编译并运行测试).结果,我必须在构建繁琐的测试后手动运行它.
Makefile.am 在test文件夹中看起来像这样:
check_PROGRAMS = prog_test
prog_test_SOURCES = test_main.cpp ../src/class1.cpp class1_test.cpp class2.cpp ../src/class2_test.cpp ../src/class3.cpp ../src/class4.cpp
prog_test_LDADD = $(BOOST_FILESYSTEM_LIB) $(BOOST_SYSTEM_LIB) $(BOOST_UNIT_TEST_FRAMEWORK_LIB)
Makefile.am 在根文件夹中:
SUBDIRS = src test
dist_doc_DATA = README
ACLOCAL_AMFLAGS = ${ACLOCAL_FLAGS} -I m4
运行test/prog产生输出:
Running 4 test cases...
*** No errors detected
(我不认为你需要我的测试用例的内容才能回答我的问题,所以我现在省略了它们)
那么我怎样才能automake在每次跑步时运行我的测试make check？
automake autoconf unit-testing makefile boost-unit-test-framework
有没有办法像git clean -d -x -f使用GitPython一样？
我需要重置工作目录,并希望摆脱所有未版本控制的文件而不删除整个文件夹(除了.git)并再次签出.
有没有一种方法可以使用Frama-Cslicing插件为特定的C assert语句计算切片？
例如，给出以下代码：
int main() {
double a=3;
double b=4;
double c=123;
assert(b>=0);
double d=a/b;
c=a;
return 0;
}
我想得到以下切片assert(b>=0);：
int main() {
double b=4;
assert(b>=0);
return 0;
}
我用来boost::filesystem搜索和处理目录中的文件。boost::filesystem::is_regular_file()但我只想处理文本文件（或至少忽略二进制文件），而不是处理每个文件（通过使用检查）。
即使文件没有扩展名，有没有办法可以实现这一点？
我非常感谢独立于平台的解决方案。