Palindrome with minimal character insertion

Hi!

I need a program which calculates it, that MINIMALLY!!! how many character is needed to insert the word to make a palindrome.


Input specification:

in.txt text substance (string) first and one single of his row have an "S" word which max length is 2000 character and "S" all "c" his character:
'a' <= c <= 'z' or 'A' <= c <= 'Z'


Output specification:

The out.txt text substance first row is an "m" not negative number. This is the MINIMAL number of characters whitch is needed to insert the "S" word to make a palindrome.
The other "m" rows needed to have an one insertion. In all rows have an i x pair separated with a white space, where i is that position, after which is necessary to insert an x character.
The numbers of positions as the number after the insertions done already to be understood. The first number of character is the 1.

Not allowed to write the out.txt to tha standard output, so i can see the content of out.txt with the cat out.txt command.

Time limit: 0.3 s
Memory limit: 32 Mb

Such as:

in.txt
eleme

out.txt
2
1 m
2 e

(this was from it : emeleme)

I have a code, but it is give an not minimal answer :/

such as:

in.txt
cplmjqtxsufsqlinyugq

out.txt with my program is:
19
0 q
1 g
2 u
3 y
4 n
5 i
6 l
7 q
8 s
9 f
10 u
11 s
12 x
13 t
14 q
15 j
16 m
17 l
18 p

but it's not the minimal number of charactes which is needed to insert

My code:

Code:

#include <iostream>
#include <fstream>
#include <string.h>
#include <sstream>

using namespace std;

string insert(string str, int pos, char character){
        string word = str.substr(0,pos);
        word += character;
        word += str.substr(pos);
        return word;
}

int main() {
    ifstream BemenetF;
    BemenetF.open("in.txt");
    if (BemenetF.is_open()) {
    string szo = "";
    int szohossz = 0;
    int cserenr = 0;
    int elolrol = 0;
    int hatulrol = 0;
    
    string ki[2000] = "";
    
    
       getline (BemenetF,szo);

            szohossz = szo.size();

    int i = 0;
    int kin = 0;
    while ( szohossz > ( elolrol + hatulrol ) ){
        if ( szo[elolrol] != szo[szohossz-1-elolrol] ){
            szo = insert(szo,elolrol,szo[szohossz-1-elolrol]);
            stringstream szoveges;
            szoveges << elolrol;
            ki[kin] = szoveges.str()+" "+szo[szohossz-elolrol]+"\n";
            elolrol++;
            cserenr++;
            kin++;
            
        } else {
            elolrol++;
        }
        szohossz = szo.length();
        i++;
    }
    ofstream Kimenet("out.txt");
    Kimenet << cserenr << "\n";
    for(int j=0; j<=kin; j++) {
        Kimenet << ki[j];
    }
    
    }

    

return 0;
}

But it s not minimal

I tried to solve it on many manners, but did not succeed. The Levenshtein algorithm maybe give an optimal answer, but i just needed the insertion of this algorithm without delete etc., but i dont understand this algorithm.

This is very important for me, but already totally away I am becoming embittered, how my program does not work well

If somebody can please help, thank you!

John

 

> but it's not the minimal number of charactes which is needed to insert

What is the minimal number of characters which is needed? What output do you expect for the 20-character string "cplmjqtxsufsqlinyugq"? (Looks OK to me, but I might be missing something)

 

unfortunately i dont know it exectly, because the system what checks it dont show the optimal answer just : Wrong output

The system is checks the program to sixteen different case, and i got one correct, where the answer is optimal, but in specila cases such as: "cplmjqtxsufsqlinyugq" dond works good


but such as:

input:
arbbaz

My program answer:
zabbrbbaz

But this is the minimal:
zarbbraz

 

How can you know the output is wrong when you don't know what the output should be?

The output looks correct to me because if you're inserting ABCDE to make a palindrome you would expect the result to be EDCB, resulting in EDBCABCDE, which is exactly what you get for the 20-character string cplmjqtxsufsqlinyugq, i.e the 19 letters plmjqtxsufsqlinyugq in reverse order.

There appear to be some inaccuracies in your post. For input arbbaz the output would be zabbr, giving zabbrarbbaz. Please check carefully before posting, especially with these nonsense-strings.

 

as i m a student of mca 1st sem i really don't know c very well like you(after seeing your codes).but i suggest you a procedure which may help you.i am not eble to write programme in this tropic that's why i feal sorry for you.But if you follow my procedure and write a programme on it with respect to size and time i think it may be right.

procedure:-

1.get an counter.
2.from the begining you consider the characters as a middle value(start form the 2nd character not the first because it does not have both end)
3.start checking both end of the guessing midlle value to compare if it is equal increase the counter.
4.go on 3rd process for all characters.
5. check for which position counter is greater.
6.consider this position as a middle.
7.start checking both side if it is equal go for next character and if it is not then add same character at the side which have minimum character.and go on.
8.after this process if you have some characters in minimam side just ad those characters to other end in reverse order.
9.and if counter is zero consider the first value as middle nd add other end characters in reverse order at the begining.

for example:-

input:-uhytfgfhjkjhfwj

for the position 10 counter is 3 which is greater than other position.
for g it is 1.
set k as middlle.
and follow the process.


output:-jwuhytfgfhjkjhfgftyhuwj


if i can ittle bit help you please rply nd if it is solved please send the programme, i am very much involved in this programme. waiting for your rply.

Your Go4expert brother.

 

Firstly:
The english is not my native language

Furthermore, i konw that, because the specification says to "...program which calculates it, that MINIMALLY!!!..." and then the answer is not minimally --> not correct

and:

input : arbbaz

cat out.txt :

3
0 z
2 b
3 b

---> zabbrbbaz

but the optimal:

2
0 z
5 r

zarbbraz

so...

In many cases give an optimal answer but no until all of them, and this is my problem

 

Yes I know English is not your first language, but it's not language inaccuracies I'm talking about. What I'm talking about is mainly this:

Since you know this is wrong, going by what you've said, you must know HOW it is wrong. So you need to explain why it is wrong to me, because to me it looks correct.

Regarding arbbaz, it wasn't clear to me initially that the minimal insertion for this is to insert Z and R into the gaps _arbb_az, making zarbbraz. Yes, it will be more tricky if you're not just reversing the string. But in any case I still need to know why plmjqtxsufsqlinyugq(reversed) is the wrong output for cplmjqtxsufsqlinyugq and exactly what output you DO expect, i.e. what would be correct.

 

ok

If this is the optimal answer for this input : cplmjqtxsufsqlinyugq
....

19
0 q
1 g
2 u
3 y
4 n
5 i
6 l
7 q
8 s
9 f
10 u
11 s
12 x
13 t
14 q
15 j
16 m
17 l
18 p

...this is 20 character
but the txt file size is 21 byte, so the file have an Enter behind the word
so when the system is checks my program the input size is 21 byte, maybe this may influence it? ( so this is the optimal just of an enter not good? /sorry if it is not correct in English/ )

 

If i make this:

ofstream Kimenet("ki.txt");
Kimenet << cserenr << "\n";
for(int j=0; j<=kin; j++) {
Kimenet << ki[j] << "\n"; <---- new line !

}
//cout << szo << "\n"; /

the otuput:

19
0 q

1 g

2 u

3 y

4 n

5 i

6 l

7 q

8 s

9 f

10 u

11 s

12 x

13 t

14 q

15 j

16 m

17 l

18 p
<--- so in here made two new line. Maybe it is the problem. Any idea, how it is possible to solve this? (just an attempt :/ )
<---
h******@linux4: ....

 

Not sure, but maybe you could try not sending a \n to the file.
This might be something you need to check with your tutor. Automated program checkers that just print "no that's wrong" without telling you why aren't a lot of use.

 

Yes, he told me about the \n the end of line.
I tried it,now the row checks it until the end only, and does not take the row break into consideration,but no improvement