检查两个字符串的顺序是否相同
如何在javascript中编写函数以返回两个字符串之间共享的字母数量（按顺序）。检查两个字符串的顺序是否相同
例如：如果两个字符串read和bread，它应该返回4.
我想使用循环莫名其妙的，但现在看来，这将是非常令人费解了很多迭代的，我不知道从哪里开始。
有没有办法实现这个使用正则表达式？可能，得到匹配的子字符串？长度然后可以从substring.length
我想我会做的是：
- 查找与两个字符串
- 对于每一个这种的字符集，找到角色的每个实例的最长匹配串
寻找共同的字符将只是一个线性通过每个字符串，建设集，然后相交集。它不仅有助于跟踪字符，而且还能跟踪索引（字符串中的位置）。这样，当你做第二部分时，你不必搜索字符串来再次找到角色。
请不要为此投票;等到有人更聪明的时候给它一个尝试:-)（当然，你可以投我一票。）
Here is a jsfiddle带有一个实现。下面是执行这项工作的JavaScript函数：
function longestSharedSequence(str1, str2) {
var seqs = {
longest: null,
all: []
};
function setOfChars(s) {
var rv = {},
c;
for (var i = 0; i < s.length; ++i) {
c = s[i];
if (rv[c]) rv[c].push(i);
else rv[c] = [i];
}
return rv;
}
function intersect(set1, set2) {
var rv = {};
for (var c in set1) {
if (set1.hasOwnProperty(c) && set2.hasOwnProperty(c)) {
rv[c] = [set1[c], set2[c]];
}
}
return rv;
}
function getSeq(pos1, pos2) {
var seq = [str1[pos1]],
i, j;
for (i = pos1 + 1, j = pos2 + 1; i < str1.length && j < str2.length && str1[i] === str2[j]; ++i, ++j)
seq.push(str1[i]);
return seq.join('');
}
function getSeqs(positions) {
var i, j, p1 = positions[0],
p2 = positions[1],
seq;
for (i = 0; i < p1.length; ++i) {
for (j = 0; j < p2.length; ++j) {
seq = getSeq(p1[i], p2[j]);
seqs.all.push(seq);
if (seqs.longest === null || seq.length > seqs.longest.length) {
seqs.longest = seq;
}
}
}
}
var set = intersect(setOfChars(str1), setOfChars(str2));
for (var c in set) {
if (set.hasOwnProperty(c)) {
getSeqs(set[c]);
}
}
return seqs.longest;
}
REGEX无法轻松完成。你应该使用嵌套循环。
在这个例子中使用的代码：
function similarity(str1, str2) {
count = 0;
for (i = 0; i < str1.length; i++) { //Loop through the letters of the first string
for (j = i+1; j <= str1.length; j++) { //Loop through the letters of the first string, starting from the letter in i.
sub = str1.substring(i, j); //Slice the first string from i to j.
//console.log(sub, count, str2.indexOf(sub), j, i);
if (str2.indexOf(sub) != -1) { //If the sliced string is found in the second string
if (count < sub.length) { //If the count I currently have is lower then the current match I found
count = sub.length;
}
}
}
}
return count;
}
alert(similarity('zzomg', 'omg'));
有没有那么多的迭代，因为我以为。有n+(n-1)+n(n-2)+... = n^2-n它应该没有歇斯底里的字符串（如50个字母）罚款。
也许不那么容易，但似乎是可能的。看看我的答案。 :-) – Qtax
正则表达式的免费版本
chaine1 = "bread";
chaine2 = "read";
if(chaine1.length <= chaine2.length){
count = chaine1.length;
}
else{
count = chaine2.length;
}
var numberOfCharacterMatching = 0;
for (var i =0; i<count; i++){
if(chaine1.charAt(i) == chaine1.charAt(i)){
numberOfCharacterMatching++
}
}
alert(numberOfCharacterMatching++);
你的代码在“omgzomg”vs“omgomg”上失败（应该返回3，返回6） –
您应该使用其他算法答案之一。
这就是说，这里是一个正则表达式驱动的解决方案，只是为了好玩。在Perl中为了方便而实现，相同的表达式可以在JavaScript中工作。
sub longest_common_substr_len{
my $s = "$_[0]|$_[1]";
my $l = 0;
$l = length > $l? length: $l for $s =~ /(?=([^|]+)(?=[^|]*\|[^|]*\1))./g;
return $l;
}
正则表达式查找所有*共同子串，并且循环获得的最大长度。
它通过将两个字符串连接到一个特殊的分隔符（在这种情况下不能出现在字符串中，|），然后使用正则表达式来查找（“本地最长”）子字符串（在每个字符处）在分隔符之前和之后。
外部超前封装用于一次只推进一个字符。没有它，“zomg”和“zoomg”只会给2，因为“zomg”中的“zo”已经被使用而不允许“omg”匹配。
say longest_common_substr_len "read", "bread";
say longest_common_substr_len "omgzomg", "omgomg";
say longest_common_substr_len "zomg", "zoomg";
输出：
4
3
3
function longSubstrings(s1, s2, wbr, casesense){
var temp= '', long= [], tem, tem2, str1, str2, len= 2, ax, L, i= 0;
if(s1.length<s2.length){
tem= s1;
s1= s2;
s2= tem;
}
// whole words match faster, if appropriate:
wbr= wbr? ' ':'';
// you can force a case sensitive match:
str1= !casesense? s1.toLowerCase():s1;
str2= !casesense? s2.toLowerCase():s2;
// normalize spaces:
str1= str1.replace(/ {2,}/g, ' ');
str2= str2.replace(/ {2,}/g, ' ');
if(str1.indexOf(str2)!= -1) return s2;
str1= str1.split(wbr);
L= str1.length;
while(i<L){
tem= tem2= str1[i];
ax= str2.indexOf(tem);
while(ax!= -1){
++i;
if(tem2.length>= len){
len= tem2.length;
long= long.filter(function(itm){
return itm.length>= len;
});
long.push(tem2);
}
tem2+= wbr+str1[i];
ax= str2.indexOf(tem2);
}
++i;
}
return long;
}
var s1= 'oie ja s a n y t nc eedjib n ife ks aio m io gna red dogext x ia a dso zcq a a w eadz tie s matsa fw t seno e se pi iz t s j sv b n is t h toa p q osrf o tj e s ine to e io no xo sss jfytai oooic v puieo nnoveya ktnxk atl endtan uiu n s i enhro a a w k s s nlno iai ouex a t pals tnshp ia ais ga dnog rewen z ia bs t bbnn yeq sviiaio tto qe tnoimetn ntsoei i nsut oteh r iynnw ee gos moemtehlt k az q ri svft sc oot naagtc asste nl';
var s2= 'q meael a n o oia d fntqss ne assto nxs n y nx aoeog pho ev t n ao ste o it eoshi j aii x s infs g a il nho t alj ot isw ic ae si k oorateaw ts iug t b oi tn i m e vnos ss o jtn enoik kaon zseeaaitialsu ej a in ays t a nzyv m ibst sxuse t l eto od zs e y os zvinaieks w wq to ce ia ufs v k mrz e n taen d endtbatn tpteiu f gx hboati m o iieac op nef t atyno n p iatb cqaicsn d tt po r oae n n gsq nrne oe ij red doga st eowsiie snhr';
longSubstrings(s1, s2);
//checks by character
// returned value: (Array)
red dog
longSubstrings(s1, s2, 1);
//checks whole words
//returned value: (Array)
red
// Older browsers need a shim for the filter method.
(or just write a loop for the filter)
if(![].filter){
Array.prototype.filter= function(fun, scope){
var T= this, A= [], i= 0, itm, L= T.length;
if(typeof fun== 'function'){
while(i< L){
if(i in T){
itm= T[i];
if(fun.call(scope, itm, i, T)) A[A.length]= itm;
}
++i;
}
}
return A;
}
}
我添加一个实现我的回答如果你有兴趣。 – Pointy