Thursday, March 17, 2016

All palindromic contiguous substring !

This is so far what I have come up with ! I think there are better ways to do this .  : ) )
But it 's working for my problem
:-P


Here's to the code - >

//Sorry this doesn't work ! I will edit it when I'm busy :-/

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
@_@
catGotBored
@_@
*/

#include<bits/stdc++.h>
using namespace std;
int isPalindrome[100][100];
map<string,int>isThere;
void all_palindromic_conti_sub_str(string s)
{
    int N = s.length();
    //Lets find all such palindromes with length 1 . Easy , huh ?
    for(int idx = 0; idx<N; idx++)
        isPalindrome[idx][idx] = 1;

    //Lets find all such palindromes with length 2 . Easy again !!
    for(int idx = 0; idx < N -1 ; idx++)
        isPalindrome[idx][idx+1] = (s[idx] == s[idx+1] );

    //Now,lets do it for all lengths < = N

    //Idea is simple :
    //If I know s[i...j] is a palindrome then s[i-1.....j+1] is a palindrome
    //if and only if s[i-1] == s[j+1]

//O(N^2) for marking only

    for(int idx = 0 ,len = 3; idx <= N -len; idx++,len++)
    {
        for(int jdx = idx + len -1 ; jdx < N ; jdx ++ )
        {
            isPalindrome[idx][jdx] = isPalindrome[idx+1][jdx-1] & s[idx] == s[jdx] ;
        }


    }


    /

//Bad approach : O(N^3 * log (N)) -> Need to do better //
    for(int ff = 0; ff<N; ff++)
        for(int ss = 0; ss<N; ss++)
            if(isPalindrome[ff][ss])
            {
                string temp;
                for(int xfsx = ff ; xfsx <= ss  ; xfsx++)
                    temp+=s[xfsx] ;        //    cout<<s[xfsx]; //Every palindromes non distinct ones too
                if(isThere[temp] == 0)
                {
                    cout<<temp;
                    isThere[temp]++;
                    cout<<endl;
                }

            }





}

int main()
{
    string str_ = "aassaa";
    memset(isPalindrome,0,sizeof(isPalindrome)); // just for nothing 
    all_palindromic_conti_sub_str(str_);
    return  0;
}

No comments:

Post a Comment