Help us understand the problem. What is going on with this article?

[Java]年俸1000万の会社の試験問題(JavaではなくPHPで実装)

More than 5 years have passed since last update.

4種類のアルファベット "A,C,G,T" から成るn文字の文字列のうち、
"AAG"という並びが含まれる文字列を全て列挙するプログラムを書きなさい。
ただし、nは3以上の整数とし、文字列内に同じアルファベットが出現しても構わないものとし、
出力順序は問わないものとします。
http://alpha.cgios.net/alpha/cgios

速度的な問題もあるのでできれば, 重複を省く処理を入れたくはないのだが, 入れざるを得ない・・・

<?php 
/**
 * 任意の重複しないA, C, G, Tから成る長さn-3から成る文字列に対して, その文字列の任意の箇所に文字列"AAG"を埋め込んで
 * 得られる文字列は, 題意を満たす. ただし, この方法で求めた文字列には重複が存在する. そこで重複を全て省いた結果が求める
 * 文字列集合である.
 */

function padZero($string, $length) {
    if (strlen($string) < $length) {
        return padZero("0".$string, $length);
    }
    return $string;
}

function insertString($base_string, $insert_string, $position) {
    $length = strlen($insert_string);
    $value1 = substr($base_string, 0, $position);
    $value2 = $insert_string;
    $value3 = substr($base_string, $position, strlen($base_string));
    return $value1.$value2.$value3;

}

function solve($n) {
    $key = "002";
    $value;
    $hash = array();
    $answer = array();
    for ($i = 0; $i < PHP_INT_MAX; $i++) {
        $value = base_convert($i, 10, 4);
        if (strlen($value) <= $n - 3) {
            $hash[] = padZero($value, $n - 3);
        } else {
            break;
        }
    }

    for ($i = 0, $size = count($hash); $i < $size; $i++) {
        for ($j = 0, $length = strlen($hash[$i]) + 1; $j < $length; $j++) {
            $value = insertString($hash[$i], $key, $j);
            $answer[$value] = true;
        }
    }
    $hash = null;

    $count = 0;
    $replace_from = array("0", "1", "2", "3");
    $replace_to = array("A", "C", "G", "T");
    foreach($answer as $key => $value) {
        echo str_replace($replace_from, $replace_to, $key)."\n";
        $count ++;
    }
    echo "Count: $count\n";
}

// 実行
solve(10);
?>

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away