人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

●質問者: leva
●カテゴリ:コンピュータ ウェブ制作
✍キーワード:23 ABC PHP ほげほげ コード
○ 状態 :終了
└ 回答数 : 2/2件

▽最新の回答へ

1 ● KeyKey
●50ポイント

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

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

マルチバイトにするとややこしくなるので説明は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文字区切りで比較し

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

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

◎質問者からの返答

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

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

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


2 ● ヨネちゃん
●65ポイント ベストアンサー

一致する文字「ー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>";
}
?>

で可能です。

◎質問者からの返答

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ