Algorithm Problem

i have a question for dynamic programming can anyone help me to solve this ?

we have a sequence of character and have a set of sub sequence …
i want to find largest sub sequence contain this set
for example :
input :
A AB BA CA BBC
.
ABABACABAABC

out put :
11 : ABABACABAAB

output explain :
first see A
we can create it by A in set.
next have AB
can create by AB
next have ABA
can create with A and AB

and so on …

longest prefix is ABABACABAAB and its len is 11;

where is the question??

sorry … i edit this …

i am not able to understand the question . Can you provide the link?

there is no link …
i explain it

we have string of character such as : ABABACABAABC
and have many substring like below :
A
AB
BA
CA
BBC

we want to find size of largest string can make with this substring …

Can you explain the output??
Are you trying to say that we are given a original string and a number of substrings and we have to obtain maximum size of string by combining these substrings that must be present in the original string.

okay.
we travers string
first see A
we can create it by A in set.
next have AB
can create by AB
next have ABA
can create with A and AB

i want to find longest prefix from string can make with this set
and return the lenght.

I guess there must be a problem statement for this or a similar question you are asking for.

Sharing it would give a better understanding of the problem.

1 Like

i think this problem is similiar to codeforces global round 3 - problem A
if i m right then …
this problem is not the dynamic programming problem
it’s a simple math problem
link of codeforces problem A
https://codeforces.com/contest/1148/problem/A

solution of this problem
https://codeforces.com/contest/1148/submission/54923942

1 Like

ye i understand its not dp but it is not true solution … we have set of any character … but this problem had 3 char and they can comlex … A B AB BA CA …

we have string of character such as : ABABACABAABC
and have many substring like below :
A
AB
BA
CA
BBC

.
first see A
we can create it by A in set.
next have AB
can create by AB
next have ABA
can create with A and AB

i want to find longest prefix from string can make with this set
and return the lenght.

1 Like

I think the approach is that you have to check all the possibilities for a given string.

See, in this example,in the beginning for string ABABACABAABC we have two options :-A and AB.
So, what we do we will check for both cases, we make a recursive function in which two parameters are passed. The first one will be new string and the second one will be the length we have traversed.And this way we proceed.
And we will return the value which will give us the maximum length.
MY code-
// In this code i assumed that the number of substrings are given.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<string> v;

int count1=0;
int recursion(string s, int l)
{

     int k = l;
    if(s.length()==0) return 0;

    for(int j=0;j<v.size();j++)
    {
        l=k;
        string k = v[j];
        if(s.substr(0,k.length())==k)
        {

                recursion(s.substr(k.length(),s.length()-k.length()),l+= k.length());
        }
        count1=max(count1,l);
    }

    return count1;
}

int main()
{
    string s;

    cin>>s;
    int n;
    cin>>n;
    cin.ignore();
    for(int i=0;i<n;i++) {
        string p;
        cin>>p;
        v.push_back(p);
    }

    cout<<recursion(s,0)<<endl;

}

1 Like

I think it can be optimised using dp. I will try this approach later and will let you know.:grinning:

It’s work for some … i don’t know work for all test case because my timeLine dead …
if i understand let you know…
thank you.

Ok you can optimize the code using dp ,try yourself and if you will not be able to solve let me know.

Can I have another way to connection with you please?
telegram? email ? etc …

Sure i am on facebook.

Oops i’m not on facebook…

:joy::joy:Then i think you are also not on whatsapp.

but i am :joy::joy::joy::joy: