문자열 안에 같은 문자열을 포함하고 있는지 확인하는 알고리즘으로 어떤게 좋을까요?

Question

이번 두 문자열안에 같은 문자열을 가지고 있는지 확인하는 알고리즘으로levenshtein distance 라는 알고리즘을 학습했습니다.다만, 이 알고리즘은 시간복잡도가 대략 O(nm)이라서, 좋지 못한 것 같습니다.그래서, String s1 &#61; &#34;CAABCADSE&#34;; String s2 &#61; &#34;BACADFG&#34;; ~~~~~ String s10000 &#61; &#34;AD&#34;;와 같이 수많은 문자열이 있을 때, 가장 비슷한 문자열을 두개를 찾으시오.라는 상황이 주어졌을 때현재예시에서 보이는대로 보면s1를 기준으로 s2가 같은 문자열로 CAD가 있어 s10000 보다 비슷한 문자열을 가지고 있습니다.그래서 levenshtein distance 라는 알고리즘을 활용할 경우 메모리 초과가 발생하네요...이와 같이 비슷한 문자열을 찾기 위해서는 어떤 알고리즘을 사용해야할까요?단순 반복문으로 투 포인터를 활용해야할까요?팁 주신다면 정말 감사하겠습니다!

mirheeoj · Answer

효율과는 별개로 메모리 초과가 나온다는 부분이 잘 이해가 되지 않습니다. 이건 chatgpt가 생성한 코드인데, 이런 식으로 하면 딱히 메모리가 증가할 부분이 없어 보여요. 유사성이 수치로 주어지고 최고기록과 그 문자열 페어만 메모리에 남기게 되거든요. public static (string, string, int) FindMostSimilarPair(List<string> strings) { string mostSimilarPair1 = ""; string mostSimilarPair2 = ""; int maxSimilarity = int.MaxValue; for (int i = 0; i < strings.Count; i++) { for (int j = i + 1; j < strings.Count; j++) { int similarity = CalculateLevenshteinDistance(strings[i], strings[j]); if (similarity < maxSimilarity) { maxSimilarity = similarity; mostSimilarPair1 = strings[i]; mostSimilarPair2 = strings[j]; } } } return (mostSimilarPair1, mostSimilarPair2, maxSimilarity); }

DoLetgitit · Answer

public static String findLongestCommonSubstring(char[] c1, char[] c2) { int[][] dp = new int[c1.length + 1][c2.length + 1]; int maxLength = 0; int endIndex = 0; for (int i = 1; i <= c1.length; i++) { for (int j = 1; j <= c2.length; j++) { if (c1[i - 1] == c2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLength) { maxLength = dp[i][j]; endIndex = i - 1; // or j - 1, since both indices will be the same } } } } if (maxLength == 0) { return ""; // No common substring found } return new String(c1).substring(endIndex - maxLength + 1, endIndex + 1); }

문자열 안에 같은 문자열을 포함하고 있는지 확인하는 알고리즘으로 어떤게 좋을까요?

2개의 답변

기술 목록