Category String Manipulation

Absolute Path Of A Targeted File Where The Virus Is Not Present!!

Arunima Mandal Leave a comment

Problem: https://domjudge.cs.fsu.edu/public/problems/13/text

Note:

This problem intuitively resembles a tree structure. But it can be solved using a deque easily, though I think the first data structure that will come to mind is a stack, at least that was in my case. A stack would work, but eventually while accessing all the elements of the stack for length counting, then you will get how deque will serve in that case!

In the following code, there are two limiting criteria:

One is that the length of the level cannot be less than the size of the deque, if it is greater then we have already processed the subdirectory/file and we haven’t found our answer yet, so we can discard that from the deque.

And the second one is the case of checking the virus file. If the virus file is found once, then even if we get our targeted file in the same hierarchy level or in any deeper level of the same root directory, we’ll have to discard it. We have handled this checking using two variables vi and vi_level. One can use 1 variable only instead of these two to check this.

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    string target;
    cin>>target;
    string str,s,ss, ext;
    while(cin>>str)
    {
        s+=str;
        s+="\n";
    }
    int level=0, vi_level=0;
    bool flag=0, vi=0;
    deque<string> dq;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='\n')
        {
            dq.push_back(ss);
            if(flag)
            {
                if(ss==target)
                {
                    cout<<dq[0];
                    for(int i=1; i<dq.size(); i++) cout<<"/"<<dq[i];
                    return 0;
                }
                else if(ext=="virus")
                {
                    vi=1;
                    vi_level=level;
                }
            }
            ss.clear();
            level=0;
            flag=0;
            ext.clear();
        }
        else if(s[i]=='-') level++;
        else if(s[i]=='.')
        {
            if(vi && level>=vi_level) continue;
            ss+=s[i];
            flag=1;
        }
        else
        {
            if(level==0) vi=0;
            if(vi && level>=vi_level) continue;
            ss+=s[i];
            if(flag) ext+=s[i];
            while(level<dq.size()) dq.pop_back();
        }
    }
    return 0;
}

Print the Absolute File Path Of A Targeted File in C++

Arunima Mandal Leave a comment

Problem Statement: Given a file system(consisting of directories, sub-directories, and files) and a target file name, print the absolute path of that targeted file.

Input: Input would be a series of strings. The first line would be the target file name. From the next line onward, there will be multiple directories/sub-directories and file names separated by newlines. And “-” indicates the level hierarchy of each sub-directory or file. Assume that, the targeted file will always be present and will be unique in the input.

Output:

Print the path starting from the root directory name. Put a “/” in between directories, sub-directories, and files while printing the path.

Sample Input:

yes.cpp
Documents
-Homework
–DS.virus
–algo.docx
-yes.cpp
Downloads
-write.cpp
-yes.h

Sample Output:

Documents/yes.cpp

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    string target;
    cin>>target;
    string str,s,ss, ext;
    while(cin>>str)
    {
        s+=str;
        s+="\n";
    }
    int level=0;
    bool flag=0;
    deque<string> dq;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='\n')
        {
            dq.push_back(ss);
            if(flag && ss==target)
            {
                cout<<dq[0];
                for(int i=1; i<dq.size(); i++) cout<<"/"<<dq[i];
                return 0;
            }
            ss.clear();
            flag=0;
            level=0;
        }
        else if(s[i]=='-') level++;
        else if(s[i]=='.')
        {
            ss+=s[i];
            flag=1;
        }
        else
        {
            ss+=s[i];
            while(level<dq.size()) dq.pop_back();
        }
    }
    return 0;
}

Longest Palindromic Substring

Arunima Mandal Leave a comment

Note: The problem title is pretty self-explaining. Now as for the solution, it can be solved in the usual brute force method (for each starting and ending position) in O(N^3) time. Another way would be Dynamic Programming which results in O(N^2) for both time complexity and space complexity.

The following approach is also an intuitive one (though hard to come to mind at first) with better time and space complexities. It is called Expand Around Centre.

Since expanding a palindrome around its center could take O(n) time, and as we are expanding for every index of the string, the overall complexity is O(n^2). And the space complexity is O(1).

Code:

#include <bits/stdc++.h>

using namespace std;

int expandAroundCentre(string &s, int left, int right)
{
    while(left>=0 && right<s.size() && s[left]==s[right])
    {
        left--;
        right++;
    }
    return right-left-1;
}

string longestPalindrome(string s)
{
    if(s.size()==0) return "";
    int start=0, ans=0;
    for(int i=0; i<s.size(); i++)
    {
        int len1=expandAroundCentre(s,i,i); //for odd length
        int len2=expandAroundCentre(s,i,i+1); //for even length
        int len=max(len1,len2);
        if(len>ans) //if len is greater than previous palindromic length
        {
            start=i-(len-1)/2; //for left side of i
            ans=len;
        }
    }
    return s.substr(start,ans);
}

int main()
{
    string s;
    cin>>s;
    cout<<"The longest palndromic substring is "<<longestPalindrome(s)<<endl;
    return 0;
}

Longest Common Prefix of a String

Arunima Mandal Leave a comment

Brute-Force (Vertical Scanning):

Here we are returning an empty string if no common prefix is found.

Time Complexity: O(S) where S is the sum of all characters present in the vector. Or we can say O(mn) where m is the length of the vector and n is the length of the strings (assuming of highest limit) inside the vector.

Space Complexity: O(1) as constant space for the answer only.

#include <bits/stdc++.h>

using namespace std;

string longestCommonPrefix(vector<string>& strs) {
    string ans="";
    for(int j=0; j<strs[0].size(); j++)
    {
        char ch=strs[0][j];
        for(int i=1; i<strs.size(); i++)
        {
            if(j>=strs[i].size() || strs[i][j]!=ch)
            {
                return ans;
            }
        }
        ans+=ch;
    }
    return ans;
}

int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

Binary Search:

The trick to using the binary search in this problem is to find out the minimum length string first, and then apply binary search to it.

Time Complexity: O(S*log(n)) where S is the sum of all characters in the vector and n is the size of the length of the minimum string.

Space complexity: O(1).

#include <bits/stdc++.h>

using namespace std;

bool isCommonPrefix(vector<string>& strs, int len)
{
    string s=strs[0].substr(0,len);
    for(int i=1; i<strs.size(); i++)
    {
        if(strs[i].substr(0,len)!=s) return false;
    }
    return true;
}

string longestCommonPrefix(vector<string>& strs) {
    string mini_str;
    int mini=300;
    for(int i=0; i<strs.size(); i++)
    {
        if(strs[i].size()<mini)
        {
            mini=strs[i].size();
            mini_str=strs[i];
        }
    }
    if(mini==0) return "";

    int low=1; //Can't initialize it to 0 as we are considering length
    int high=mini;
    while(low<=high)
    {
        int mid=low+(high-low)/2;
        if(isCommonPrefix(strs, mid)) low=mid+1;
        else high=mid-1;
    }
    return strs[0].substr(0,(high+low)/2);
}


int main()
{
    vector<string> v;
    int n;
    cout << "Enter the no. of string you want to compare" << endl;
    cin>>n;
    cout<<"Enter the strings"<<endl;
    string s;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        v.push_back(s);
    }
    cout<<"The longest common prefix is "<<longestCommonPrefix(v)<<endl;
    return 0;
}

SPOJ – ACMCEG2B – FIGUREFUL

Arunima Mandal Leave a comment

Problem Link: http://www.spoj.com/problems/ACMCEG2B/

Solution:

#include <bits/stdc++.h>

#define pf                  printf
#define sf(a)               scanf("%d",&a)
#define sfl(a)              scanf("%lld",&a)
#define sff(a,b)            scanf("%d %d",&a,&b)
#define sffl(a,b)           scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)         scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)        scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d)      scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d)     scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e)   scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e)  scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a)              scanf("%c",&a)
#define ms(a,b)             memset(a,b,sizeof(a))
#define pb(a)               push_back(a)
#define db                  double
#define ll                  long long
#define ull                 unsigned long long
#define pii                 pair<int,int>
#define pll                 pair<long,long>
#define ff                  first
#define ss                  second
#define sz(x)               (int)x.size()
#define all(x)              x.begin(),x.end()
#define CIN                 ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c)       max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c)       min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define for0(i,n)           for(int i=0;i<n;i++)
#define for1(i,n)           for(int i=1;i<=n;i++)
#define forrev(i,n)         for(int i=n-1; i>=0; i--)
#define forab(i,a,b)        for(int i=a;i<=b;i++)
#define forba(i,b,a)        for(int i=b;i>=a;i--)
#define stlloop(x)          for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)           __gcd(a, b)
#define lcm(a, b)           ((a)*((b)/gcd(a,b)))
#define case1(z)            cout<<"Case "<<z<<": "
#define case2(z)            printf("Case %d: ",z)
#define PI                  acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty)        tx>=0 && tx<row && ty>=0 && ty<col
#define intlim              2147483648
#define MAX                 1000006
#define inf                 100000008

ll power(int n,int p)
{
    ll ans=1;
    for1(i,p) ans*=n;
    return ans;
}

ll m=1000001;
ll bigmod(ll n,ll p)
{
    if(p==0) return 1;
    else if(p%2==0)
    {
        ll x=(bigmod(n,p/2))%m;
        return (x*x)%m;
    }
    else return ((n%m)*(bigmod(n,p-1)%m))%m;
}


/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/

using namespace std;

map<pii,string> mp;

int main()
{
    //CIN;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,t,x,y;
    string s;
    sf(n);
    for0(i,n)
    {
        sff(x,y);
        cin>>s;
        pii z=make_pair(x,y);
        mp[z]=s;
    }
    sf(t);
    for1(z,t)
    {
        sff(x,y);
        pii w=make_pair(x,y);
        cout<<mp[w]<<endl;
    }

    return 0;
}