2つの異なる長さ・内容の文字列があります。例えば以下のような物です。

A: 「ほげほげ列車殺人事件ーABC」
B: 「大阪の23時のニュースーABC」
このように、2つの文字列には共通して存在する部分(ここでは「ーABC」)が存在します。このとき、2つの共通部分を求めるにはどうすればよいでしょうか?
言語はPHPを想定しており、できるだけ速く処理したいと思っています。実際のコードもしくはコードが書いてあるページへのリンクでの回答をお願いします。

なお、上記の例は一例であって実際には文字列の長さ・内容および共通する部分は異なるのが前提です。よろしくお願いします

回答の条件
  • 1人2回まで
  • 登録:2008/01/20 15:36:23
  • 終了:2008/01/22 06:20:24

ベストアンサー

id:yoneto164 No.2

ヨネちゃん回答回数813ベストアンサー獲得回数942008/01/21 18:23:16

ポイント65pt

一致する文字「ーABC」を得るとすれば、

<?php
$a="ほげほげ列車殺人事件ーABC";
$b="大阪の23時のニュースーABC";
$al=mb_strlen($a,"SJIS");
$bl=mb_strlen($b,"SJIS");
for($i=0;$i<$al;$i++){
	$aa[$i]=mb_substr($a,$i,1,"SJIS");
}
for($i=0;$i<$bl;$i++){
	$bb[$i]=mb_substr($b,$i,1,"SJIS");
}
for($i=0;$i<$al;$i++){
	for($j=0;$j<$bl;$j++){
		if($aa[$i]==$bb[$j]){
			if($much){
				foreach($much as $str){
					if($aa[$i]==$str){
						$ng=1;
					}
				}
			}
			if($ng!=1){
				$much[$num]=$aa[$i];
			}
			$ng=0;
			$num ++;
		}
	}
}
foreach($much as $print){
	echo $print;
}
?>

で可能です。

また、一致する文字列ということであれば、

「ニュース」の「ー」も一致するので、

「ー」と「ーABC」になるのですが、

その場合は

<?php
$a="ほげほげ列車殺人事件ーABC";
$b="大阪の23時のニュースーABC";
$al=mb_strlen($a,"SJIS");
$bl=mb_strlen($b,"SJIS");
for($i=0;$i<$al;$i++){
	$aa[$i]=mb_substr($a,$i,1,"SJIS");
}
for($i=0;$i<$bl;$i++){
	$bb[$i]=mb_substr($b,$i,1,"SJIS");
}
for($i=0;$i<$al;$i++){
	for($j=0;$j<$bl;$j++){
		if($muchnum[$i][$j]!=1){
			if($aa[$i]==$bb[$j]){
				$much[$num]=$aa[$i];
				$muchnum[$i][$j]=1;
				for($k=1;$k<=$al-$i-1 && $k<=$bl-$j-1;$k++){
					if($aa[$i+$k]==$bb[$j+$k]){
						$much[$num] .= $aa[$i+$k];
						$muchnum[$i+$k][$j+$k]=1;
					}else{
						$j=$j+$k-1;
						break;
					}
				}
				$num ++;
			}
		}
	}
}
foreach($much as $print){
	echo $print."<br>";
}
?>

で可能です。

id:leva

ありがとうございました。

回答を読んでまとめた答えを以下に載せました。

http://note.openvista.jp/245/

2008/01/22 06:18:59

その他の回答(1件)

id:KeyKey No.1

KeyKey回答回数29ベストアンサー獲得回数42008/01/21 16:34:30

ポイント50pt

どれぐらいの長さの文字列を想定しているのかわかりませんが

とりあえず簡単に思いつく範囲で答えます。

マルチバイトにするとややこしくなるので説明は1byte文字で

<?php
$a = "0123456789";
$b = "abc345ghij";
//片方の文字列の長さを取得
$len = strlen($a);


for ($i = 0; $i < $len; $i++) {
    for ($j = 1; $j <= $len - $i; $j++) {
        //$i文字目から$j文字目までを切り出す
        $rest = substr($a, $i, $j);
        //$bに含まれていれば配列に格納
        if (preg_match("/" . $rest . "/", $b, $match)) {
            $result[] = $rest;
        }
    }
}

print_r($result);
?>
Array ( [0] => 3 [1] => 34 [2] => 345 [3] => 4 [4] => 45 [5] => 5 )

これでN!回の比較で求めることができます。

これを発展させて、まず1文字区切りで比較し

一致しない文字を含んでいる時の処理を飛ばすようにすると

一気に処理数を減らせると思います。

id:leva

ありがとうございました。

回答を読んでまとめた答えを以下に載せました。

http://note.openvista.jp/245/

2008/01/22 06:18:52
id:yoneto164 No.2

ヨネちゃん回答回数813ベストアンサー獲得回数942008/01/21 18:23:16ここでベストアンサー

ポイント65pt

一致する文字「ーABC」を得るとすれば、

<?php
$a="ほげほげ列車殺人事件ーABC";
$b="大阪の23時のニュースーABC";
$al=mb_strlen($a,"SJIS");
$bl=mb_strlen($b,"SJIS");
for($i=0;$i<$al;$i++){
	$aa[$i]=mb_substr($a,$i,1,"SJIS");
}
for($i=0;$i<$bl;$i++){
	$bb[$i]=mb_substr($b,$i,1,"SJIS");
}
for($i=0;$i<$al;$i++){
	for($j=0;$j<$bl;$j++){
		if($aa[$i]==$bb[$j]){
			if($much){
				foreach($much as $str){
					if($aa[$i]==$str){
						$ng=1;
					}
				}
			}
			if($ng!=1){
				$much[$num]=$aa[$i];
			}
			$ng=0;
			$num ++;
		}
	}
}
foreach($much as $print){
	echo $print;
}
?>

で可能です。

また、一致する文字列ということであれば、

「ニュース」の「ー」も一致するので、

「ー」と「ーABC」になるのですが、

その場合は

<?php
$a="ほげほげ列車殺人事件ーABC";
$b="大阪の23時のニュースーABC";
$al=mb_strlen($a,"SJIS");
$bl=mb_strlen($b,"SJIS");
for($i=0;$i<$al;$i++){
	$aa[$i]=mb_substr($a,$i,1,"SJIS");
}
for($i=0;$i<$bl;$i++){
	$bb[$i]=mb_substr($b,$i,1,"SJIS");
}
for($i=0;$i<$al;$i++){
	for($j=0;$j<$bl;$j++){
		if($muchnum[$i][$j]!=1){
			if($aa[$i]==$bb[$j]){
				$much[$num]=$aa[$i];
				$muchnum[$i][$j]=1;
				for($k=1;$k<=$al-$i-1 && $k<=$bl-$j-1;$k++){
					if($aa[$i+$k]==$bb[$j+$k]){
						$much[$num] .= $aa[$i+$k];
						$muchnum[$i+$k][$j+$k]=1;
					}else{
						$j=$j+$k-1;
						break;
					}
				}
				$num ++;
			}
		}
	}
}
foreach($much as $print){
	echo $print."<br>";
}
?>

で可能です。

id:leva

ありがとうございました。

回答を読んでまとめた答えを以下に載せました。

http://note.openvista.jp/245/

2008/01/22 06:18:59

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません