Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Наибольшая общая строка / 7 сообщений из 7, страница 1 из 1
28.04.2012, 19:17:24
    #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
28.04.2012, 21:21:03
    #37776428
grasoff.net
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Наибольшая общая строка
...
Рейтинг: 0 / 0
28.04.2012, 23:35:43
    #37776497
dirty_valera
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Наибольшая общая строка
grasoff.net,

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

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

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

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


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