powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Наибольшая общая строка
7 сообщений из 7, страница 1 из 1
Наибольшая общая строка
    #37776350
dirty_valera
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Здравствуйте!
Есть следующая задача.
Дано n<10 строк длинна которых меньше 10000 символов каждая.
Нужно найти наибольшую общую подстроку.
Задача сама по себе простая, но сложность в том что по времени она должна выполняться менее чем за 1,5 секунды.
Я использовал следующий алгоритм:
Искал наикратчайшую строку, делал из нее подстроки длинной меньше на 1, на 2 и т.д. и каждую подстроку сразу после создания проверял на то, чтобы она находилась в оставшихся исходных строках. Если это выполняется то строка выводится и программа закрывается.
Однако при длине входящих строк от 7000 время выполнения больше чем 1,5 сек.
Кто может, предложите какой-нибудь быстрый алгоритм, ну или способ ускорить программу.
Код прилагается :

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Word_fast {
    public static void main(String[] args) throws Exception {
        BufferedReader b = new BufferedReader( new InputStreamReader(System.in));
        String s = b.readLine();
        int n = Integer.parseInt(s);
        String str[] = new String[n];
        String stt[] = new String[n];
        for (int i =0; i<=n-1;i++){            
            str[i] = b.readLine();
            stt[i]=str[i];
        }
        for (int i =1; i<=n-1;i++){
             
            if(str[i-1].length() <= str[i].length()){
                s=str[i-1];
                str[i]=str[i-1];
                str[i-1]=s;
            }
        }
        String shortest = str[n-1];
        for(int i=shortest.length()-1;i>=0;i--){
            for(int j=i; j<=shortest.length()-1;j++){
                String st=shortest.substring(j-i,j+1);          
                int count=0;
                for(int k=0; k<=str.length-1;k++){
                    if(stt[k].contains(st)){
                        count++;
                    }
                }
                if(count==n){
                    System.out.println(st);
                    System.exit(0);
                }
            }
        }
    }
}



Заранее спасибо!
...
Рейтинг: 0 / 0
Наибольшая общая строка
    #37776428
Фотография grasoff.net
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Наибольшая общая строка
    #37776497
dirty_valera
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
grasoff.net,

Недурно...
Спасибо посмотрю:)
...
Рейтинг: 0 / 0
Наибольшая общая строка
    #37776672
dirty_valera
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
ОК. А тогда такой вопрос: там алгоритм для 2ух строк, а как мне его использовать для n строк?
...
Рейтинг: 0 / 0
Наибольшая общая строка
    #37777635
rfq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dirty_valera,

а общая построка - это что?
- входит во все исходные строки
- входит в не менее чем в 2 исходные строки
- встречается не менее чем в 2х местах, может быть и в одной исходной строке

какой алфавит используется? для символа надо 2 байта (char) или достаточно одного?

строки содержат текст на естественном языке или же это случайный набор символов?
...
Рейтинг: 0 / 0
Наибольшая общая строка
    #37778117
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dirty_valera, какая-то постановка - синтетическая. Здесь можно очень сильно выиграть
если заранее знать что строки состоят из слов (текст) и индексируя цепочки слов сильно
сокращать время поиска. Если это url-s - то соотвествтенно отбросить ненужные проверки
и искать совпадения только с начала (т.к. url по другому не substring-гуестя).
...
Рейтинг: 0 / 0
Наибольшая общая строка
    #37778315
dirty_valera
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Каждая строка состоит из не более чем 10 000 маленьких латинских букв
...
Рейтинг: 0 / 0
7 сообщений из 7, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Наибольшая общая строка
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]