给定一个query和一个text,均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如, query为“acbac”,text为“acaccbabb”,那么text中的“cba”为最长的连续出现在query中的字母序列,因此,返回结果应该为其长度3。请注意程序效率。
#include <iostream> #include <string> #include <vector> using namespace std; int main(){ string query, text; cin >> query >> text; vector<int> flag; for (int i = 0; i < query.size(); ++i){ if (text.find(query[i]) != string::npos) flag.push_back(i); } if (flag.size() == 1){ printf("1\n"); return 0; } int ans = 0, len = 0; for (int i = 0; i < flag.size(); i++){ string str = ""; str += query[flag[i]]; for (int j = i + 1; j < flag.size(); j++){ if (flag[j] - flag[j - 1] == 1){ str += query[flag[j]]; if (str.size() <= len) continue; if (text.find(str) != string::npos){ len = str.size(); if (len > ans) ans = len; } else break; } else break; } } printf("%d\n", ans); return 0; }