如何确定一个字符串是否以另一个字符串开头 [英] How to determine if one string starts with what another ends with
问题描述
我有一个短语列表:
[
"according to all known laws of aviation",
"time flies when you're having fun..."
...
]
我想在此列表中找到与输入字符串结尾匹配的所有短语.例如:
getNext("did you know that time flies w")
应该在列表中进行搜索，以匹配任何以did you know that time flies w结尾的字符串.例如，它应该返回一个至少包含time flies when you're having fun的列表，因为它以该短语的开头time flies w结尾.
我想不出任何合理的方法来做到这一点.
我唯一想到的是遍历输入中的每个字符，并检查它是否与词组的开头匹配.如果是这样，请增加一个计数器.如果在循环结束时它大于1(或其他一些数字)，则在另一个列表的短语处以及匹配数.从那里，我可以对列表进行排序，以便首先给出最接近的匹配，最后给出不那么接近的匹配.
肯定有更好的方法可以做到这一点吗?
有关背景知识，您可以看到此Repl.it项目和这个非常相似的Python问题.
我在这里回答很无奈，没有比蛮力更好的东西了……我真的很乐于经历它，但仍然希望有人会.
但是对于您的应用程序，必须在jojonas的算法上添加一些优化.您可能将在每次击键时执行此检查，并且由于它是自动完成的，因此输入的长度可能会很快增加.
第一个优化是将输入切成所检查字符串的长度. 给定长度为8的输入以及要比较长度为3的字符串，则前5次迭代不可能返回匹配项
input: "aaaaaaaa" (8)
compare: "aaa" (3)
^- first possible match for compare.startsWith()
通过将迭代器初始化为max(input.length - compare.length, 0)，可以很容易地做到这一点.
对该算法的第二个优化包括在input的其余部分内搜索compare的第一个字母的第一个索引.只要它不是compare的第一个字符，就不需要遍历每个字符，我们可以确定compare.startsWith将返回false.然后我们可以重复进行，直到找到正确的余数为止，然后再在整个过程中删除很多循环.
const phrases = ["according to all known laws of aviation", "a blessing in disguise", "a bunch", "a dime a dozen", "beat around the bush", "better late than never", "bite the bullet", "break a leg", "call it a day", "cut somebody some slack", "cutting corners", "dead tired", "easy does it", "excuse me", "get it out of my system", "get it out of your system", "get out of hand", "get something out of my system", "get something out of your system", "get your act together"];
inp.oninput = e => {
const overlaps = getOverlaps(inp.value, phrases);
makeList(overlaps);
if(logged) console.clear();
};
let logged = false;
inp.oninput();
logged = true;
// "abcde", "def"
function getOverlaps(input, list) {
return list.filter(compare => {
// single logger, just for demo
const log = (...args) => !logged && compare === "beat around the bush" && console.log.apply(console, args);
// search only in possible area
let i = Math.max(input.length - compare.length, 0); // 2
log('initial i:', i);
const first_letter = compare[0]; // "d"
let remain = input.substr(i); // "cde"
log('initial remain:', remain);
while(i < input.length) {
// jump to first letter
let index = remain.indexOf(first_letter); // 1
log('in-loop index:', index);
if(index < 0) { // not found
return false;
}
i += index; // 3
remain = input.substr(i); // "de"
log('in-loop remain:', remain);
if(compare.startsWith(remain)) { // found
return true; // =>
}
// wasn't this one, move by one char
// (will jump to next occurence of first_letter) at next iteration
i++;
remain = input.substr(i);
}
});
}
function makeList(items) {
list.innerHTML = '';
items.forEach(e =>
list.appendChild(
document.createElement('li')
).textContent = e
);
}
body{padding-bottom: 120px}
<input id="inp" value="according to all known laws of aviation to bring a beat a" autofocus>
<ul id="list"></ul>
I have a list of phrases:
[
"according to all known laws of aviation",
"time flies when you're having fun..."
...
]
I would like to find all the phrases in this list that match with the end of an input string. For example:
getNext("did you know that time flies w")
should perform a search through the list to match any string that starts with what did you know that time flies w ends with. As an example, it should return a list that at least contains time flies when you're having fun since itends with time flies w which is the start of that phrase.
I can't think of any reasonable way to do this.
The only thing I can think of is running through each character in the input and check if it matches the start of the phrase. If it does, increment a counter. If it is >1 (or some other number) at the end of the loop, at the phrase to another list, along with the number of matches. From there I could sort the list to give the closest match first, and the less close ones last.
Surely there must be a better way to do this?
For a bit of background, you can see this Repl.it project and this very similar Python question.
It is quite frustrated that I answer here, without anything better than the brute-force... I would really have enjoyed a more clever way to go through it, and still hope someone will.
But given your application, there a a few optimizations you must add on jojonas' algorithm. You are probably going to perform this check at each keystroke, and since it is an autocomplete, the input may grow in length pretty fast.
One first optimization is to cut the input to the length of the checked string. Given an input of length 8, and a string to compare of length 3, there is no way the first 5 iterations return a match
input: "aaaaaaaa" (8)
compare: "aaa" (3)
^- first possible match for compare.startsWith()
This can be quite easily done by initiating our iterator to max(input.length - compare.length, 0).
A second optimization to this algorithm consist in searching for the first index of the first letter of compare inside the remainder of input. No need to go through every characters, as long as it isn't the first one of compare we can be sure that compare.startsWith will return false. We can then repeat until we find which remainder is correct, once again removing quite a few loops in the whole process.
const phrases = ["according to all known laws of aviation", "a blessing in disguise", "a bunch", "a dime a dozen", "beat around the bush", "better late than never", "bite the bullet", "break a leg", "call it a day", "cut somebody some slack", "cutting corners", "dead tired", "easy does it", "excuse me", "get it out of my system", "get it out of your system", "get out of hand", "get something out of my system", "get something out of your system", "get your act together"];
inp.oninput = e => {
const overlaps = getOverlaps(inp.value, phrases);
makeList(overlaps);
if(logged) console.clear();
};
let logged = false;
inp.oninput();
logged = true;
// "abcde", "def"
function getOverlaps(input, list) {
return list.filter(compare => {
// single logger, just for demo
const log = (...args) => !logged && compare === "beat around the bush" && console.log.apply(console, args);
// search only in possible area
let i = Math.max(input.length - compare.length, 0); // 2
log('initial i:', i);
const first_letter = compare[0]; // "d"
let remain = input.substr(i); // "cde"
log('initial remain:', remain);
while(i < input.length) {
// jump to first letter
let index = remain.indexOf(first_letter); // 1
log('in-loop index:', index);
if(index < 0) { // not found
return false;
}
i += index; // 3
remain = input.substr(i); // "de"
log('in-loop remain:', remain);
if(compare.startsWith(remain)) { // found
return true; // =>
}
// wasn't this one, move by one char
// (will jump to next occurence of first_letter) at next iteration
i++;
remain = input.substr(i);
}
});
}
function makeList(items) {
list.innerHTML = '';
items.forEach(e =>
list.appendChild(
document.createElement('li')
).textContent = e
);
}
body{padding-bottom: 120px}
<input id="inp" value="according to all known laws of aviation to bring a beat a" autofocus>
<ul id="list"></ul>
这篇关于如何确定一个字符串是否以另一个字符串开头的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
