数组应用 例寻找两个串最长的公共子串 -通常的匹配算法复杂度0(m*n) -利用二维数组构造串之间的关系来求解 Sl=“sgabacbadfgbacst'” S2=“gabadfgab” 最大公共子串“badfg”。 算法时间复杂度Om*n) ypb@ustc.edu.cn 12 中国科学技术大学ypb@ustc.edu.cn 12 中国科学技术大学 • 例寻找两个串最长的公共子串 – 通常的匹配算法复杂度O(m*n2 ) – 利用二维数组构造串之间的关系来求解 S1=“sgabacbadfgbacst” S2=“gabadfgab” 最大公共子串“badfg” 。 算法时间复杂度 O(m*n) 数组应用