ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1517. Свобода выбора

can this problem solved with dp.
Послано runtime_error 29 июл 2013 15:07
i tried to solve this problem with dp. O(N*2) time and O(N) memory:
here is my code
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int  n;

string s,t;

string Longest_common_substr(void)
{

    int place;

    int longest=0;

    vector<int> m(n);

    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>=0;j--)
        {
            if(s[j]==t[i])
            {
                if(j!=0)m[j]=m[j-1]+1;
                else m[j]=1;
            }
            else m[j]=0;

            if(m[j]>longest)
            {
                longest=m[j];
                place=j-longest+1;
            }
            if(longest==n)return s.substr(place,longest);
        }
    }
    if(longest==0)return "";
    else return s.substr(place,longest);



}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie();
    cin>>n;
    cin>>s;
    cin>>t;
    cout<<Longest_common_substr()<<endl;
    return 0;
}

can you please suggest any modifications?