runtime_error's blog

By runtime_error, 11 years ago, In English

I see in many string problems like this: Find how many string there is of given length n, consisting only of the characters: 'a', 'b',and "c", and do not contain the substring "ab". In this problem answer of simple tests : n=0 answer=1 why answer is 1??why??

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

hello!Can you give me links , where i can read articles and some examples? Or problems(will be good in pdf)?

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

In contests it is important to know I/O routines.Let's discuss there about this task. Any links or advises will be welcomed!

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

hello,i have tried to compute longest common substring for more than 2 string.

i read dp solution in wikipedia.We can compute it with O(min(a,b)) memory and O(ab) time. but i don't know how to do this with 3 or more strings,when string sizes are two big-1000000; please help me! my wrong solution :

#include<iostream>
#include<string>
#include<algorithm>

#define MAX 1000000

using namespace std;

int  *m=new int [MAX];

string longest_common_substring(string s,string t)
{
    for(int i=0;i<MAX;i++)
        m[i]=0;

    int d;
    int longest=0;

    for(int i=0;i<t.size();i++)
    {
        for(int j=s.size()-1;j>=0;j--)
        {
            if(s[j]==t[i])
            {

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


int main()
{
    string s;
    int n;
    cin>>n;
    
    cin>>s;
    for(int i=0;i<n-1;i++)
    {
        string t;
        cin>>t;
        s=longest_common_substring(s,t);
    }
    cout<<s<<endl;
    return 0;


}

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

recently i have seen one problem on e-olimp.com.ua

this problem is about to find all 1 ≤ i < j ≤ n (n=string size) that a[i..j] is palindrome.

this is my solution:

#include<bits/stdc++.h>

using namespace std;

string pre_process(string s)
{
    int n=s.size();

    if(n==0) return "^$";

    string rev="^";
    for(int i=0;i<n;i++)
        rev+='#'+s.substr(i,1);
    rev+="#$";
    return rev;
}


long long  manacher(string s)
{
    string T=pre_process(s);
    int n=T.size();

    long long  answer=0;

    int *p=new int[n];

    int c=0,r=0;
    for(int i=1;i<n-1;i++)
    {
        int mirror=2*c-i;
        p[i]=(i<r)?min(p[mirror],r-i):0;

        while(T[i-1-p[i]]==T[i+1+p[i]])
            p[i]++;
        if(i+p[i]>r)
            c=i,r=i+p[i];


        if(p[i]>1)
            answer+=p[i]/2;
    }
    return answer;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin>>s;

    cout<<manacher(s)<<endl;

    return 0;
}

i use manacher's algorithm which time complexity is o(n),but i get TLE in last several test cases.

i know it can be solved whith suffix tree. Is is better than manacher?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

many contestant in CF use std::string which i more easy than old c style string. but many experiensed programmers use old style string . what do you think which is better .please comment about their advantages and disadventages.

Full text and comments »

Tags c++
  • Vote: I like it
  • -18
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

hello everyone,i am begginer.i have learnt few string algorithms(like Z-function,prefix function K-m-p ...) can you give me links of problems on this or another sites. thanks advance!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By runtime_error, 11 years ago, In English

i know that is not programming task at all but if you help me i will happy.

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it