文字列を操作するアルゴリズム

文字列を操作するアルゴリズムとして、ここでは文字列照合、文字列検索、文字列置換の3つをご紹介します。

文字列照合

文字列照合とは、2つの文字列が同じであるか否かを判定するアルゴリズムです。JavaでいえばStringクラスのequalsメソッドに相当します。

String str1 = "Hello";
String str2 = "Hello";
String str3 = "World";

boolean result1 = str1.equals(str2); // true
boolean result2 = str1.equals(str3); // false

<サンプルプログラム>

public class StringMatcher {
	public static void main(String[] args) {
		char[] text1 = { 'H', 'e', 'l', 'l', 'o' };
		char[] text2 = { 'H', 'e', 'l', 'l', 'o' };
		char[] text3 = { 'W', 'o', 'r', 'l', 'd' };

		System.out.println(matchStrings(text1, text2));//true
		System.out.println(matchStrings(text1, text3));//false
	}

	// 2つのchar型の配列を受け取り、文字列が一致するかどうかを判定するメソッド
	public static boolean matchStrings(char[] text1, char[] text2) {
		// 配列の長さが異なる場合、文字列は一致しない
		if (text1.length != text2.length) {
			return false;
		}

		// 配列の要素を1つずつ比較して、一致しない文字が見つかれば文字列は一致しない
		for (int i = 0; i < text1.length; i++) {
			if (text1[i] != text2[i]) {
				return false;
			}
		}

		// 全ての文字が一致した場合、文字列は一致する
		return true;
	}
}

<実行結果>

true
false

文字列検索

文字列検索【String Searching】は、与えられたテキスト内で特定の文字列(検索パターン)を探し出す操作です。テキスト内の出現箇所や一致する部分を見つけることが目的となります。

文字列検索は、テキスト内での特定のパターンの存在や出現回数を判断するために使用されます。一般的な目的は、特定の文字列やパターンがテキスト内に存在するかどうかを調べることです。検索されるパターンは、単一の文字列、単語、フレーズ、または正規表現パターンのような複雑なパターンである場合があります。

文字列検索は、テキスト処理、データベース検索、情報検索、ログ解析、テキスト解析、自然言語処理、パターンマッチングなど、さまざまな領域で重要な操作です。

一般的な文字列検索手法としては、力まかせ法(Brute-Force法)、Knuth-Morris-Pratt法(KMP法)、Boyer-Moore法などがあります。今回は、力まかせ法をご紹介します。

以下にご紹介しているアルゴリズムはJavaでいえばStringクラスのindexOfメソッドに相当します。

String text = "Hello world";
int position = text.indexOf("world"); // 6を返す

<サンプルプログラム>

public class StringMatcher {
	public static void main(String[] args) {
		char[] text1 = { 'H', 'e', 'l', 'l', 'o' };
		char[] text2 = { 'H', 'e', 'l', 'l', 'o' };
		char[] text3 = { 'W', 'o', 'r', 'l', 'd' };

		System.out.println(matchStrings(text1, text2));//true
		System.out.println(matchStrings(text1, text3));//false
	}

	// 2つのchar型の配列を受け取り、文字列が一致するかどうかを判定するメソッド
	public static boolean matchStrings(char[] text1, char[] text2) {
		// 配列の長さが異なる場合、文字列は一致しない
		if (text1.length != text2.length) {
			return false;
		}

		// 配列の要素を1つずつ比較して、一致しない文字が見つかれば文字列は一致しない
		for (int i = 0; i < text1.length; i++) {
			if (text1[i] != text2[i]) {
				return false;
			}
		}

		// 全ての文字が一致した場合、文字列は一致する
		return true;
	}
}

<実行結果>

パターンが見つかりました。インデックス: 6

文字列置換

文字列置換【String Replacement】は、ある文字列内の特定の部分文字列を別の文字列に置き換える操作です。特定のパターンを持つ文字列を別のパターンに変換することで、文字列の変換や修正を行う際に使用されます。

文字列置換の一般的な目的は、テキスト内の特定の文字列やパターンを探し出し、それを別の文字列やパターンに置き換えることです。置換は一度の操作で行われる場合もありますし、複数回の置換操作が必要な場合もあります。

例えば、以下のような状況で文字列置換は使用されます:

  • 文章内の特定の単語を他の単語やフレーズに置き換える。
  • 文字列内の特定の文字や文字列パターンを修正する。
  • 正規表現パターンに一致する部分を特定の文字列で置き換える。
  • フォーマットされたテキスト内の変数を実際の値で置き換える。

文字列置換は、多くのプログラミング言語やテキストエディタでサポートされており、組み込みの置換関数やメソッドが提供されています。これらの機能を使用することで、効率的かつ正確に文字列の置換を行うことができます。

文字列置換は、データ処理、テキスト解析、テンプレート処理、ログ処理、言語処理など、さまざまな場面で広く使用されます。

以下にご紹介しているアルゴリズムは、JavaでいえばStringクラスのindexOfメソッドに相当します。

String text = "Hello world";
String replacedText = text.replace("Hello", "Goodby"); // "Goodby world"を返す

※以下のサンプルプログラムでは、置換対象の文字列は置換前の文字列に1度しか出現しないものとします。

<サンプルプログラム>

public class StringReplacement {
	public static void main(String[] args) {
		// 置換前の文字列を定義
		char[] originalString = { 'H', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd' };

		// 置換対象の文字列を定義
		char[] targetString = { 'H', 'e', 'l', 'l', 'o' };

		// 置換後の文字列を定義
		char[] replacementString = { 'G', 'o', 'o', 'd', 'b', 'y' };

		// 置換後の文字列を表示
		System.out.println(replaceString(originalString, targetString, replacementString));
	}

	// 文字列の置換を行うメソッド
	public static char[] replaceString(char[] originalString, char[] targetString, char[] replacementString) {
		int originalLength = originalString.length;
		int targetLength = targetString.length;
		int replacementLength = replacementString.length;

		// 置換後の文字列を格納するための配列を作成
		char[] replacedString = new char[originalLength + (replacementLength - targetLength)];

		// 置換を実行
		int newIndex = 0;
		for (int i = 0; i <= originalLength - targetLength; i++) {
			boolean match = true;
			// 置換対象の文字列と一致するかチェック
			for (int j = 0; j < targetLength; j++) {
				if (originalString[i + j] != targetString[j]) {
					match = false;
					break;
				}
			}

			// 一致した場合、置換後の文字列をコピー
			if (match) {
				for (int j = 0; j < replacementLength; j++) {
					replacedString[newIndex++] = replacementString[j];
				}
				i += targetLength - 1;
			} else {
				// 一致しない場合、元の文字列をそのままコピー
				replacedString[newIndex++] = originalString[i];
			}
		}

		//残りの文字をコピー
		for (int i = originalLength - targetLength + 1; i < originalLength; i++) {
			replacedString[newIndex++] = originalString[i];
		}

		return replacedString;
	}
}

<実行結果>

Goodby world

投稿者プロフィール

山崎講師
山崎講師代表取締役
セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します!
この記事に間違い等ありましたらぜひお知らせください。