What would be the time complexity of this code?

Question

1.00/5 (2 votes)

See more:

The problem is:
1. given two string A, B (A less than B in size) find the indexes at which A or any permutation of A occurs in B.

e.g>

A : for
B : dforfdorfaaabrofasdf

ans : 1,6,13

C#

#include<iostream.h>
using namespace std;
#include<conio.h>

int main()
{
    char s[100],t[100];
    int i,j,k,l,flag;
    gets(s);
    gets(t);
    int sums,sumt;
    int lens=strlen(s);
    int lent=strlen(t);
    for(i=0;i<lent;i++)
    sumt+=t[i];
    for(i=0;i<lens;i++)
    {
        sums=0;
        for(j=i;j<i+lent;j++)
        sums+=s[j];
        if(sums==sumt)
        {
            for(k=0;k<lent;k++)
            {
                for(l=0;l<lent;l++)
                {
                    flag=0;
                    if(s[i+k]==t[l])
                    {
                        flag=1;
                        break;
                    }
                }
                if(!flag)
                break;
            }
            if(flag)
            {
                printf("%d\t",i);
                i=i+lent-1;
            }
        }
    }
    getch();
}

Posted 27-Aug-13 18:54pm

Brady Bar

Updated 27-Aug-13 21:13pm

v5

Add a Solution

Comments

[no name] 28-Aug-13 1:54am

And the question is?

Brady Bar 28-Aug-13 3:12am

What is the time complexity of this code??Would it be less than the naive algorithm.

Richard MacCutchan 28-Aug-13 3:21am

Your answer missed index 2.

Brady Bar 28-Aug-13 4:34am

No, the occurences should not overlap.

Richard MacCutchan 28-Aug-13 3:24am

You could also look at these functions.

2 solutions

Solution 1

if it is a homework from your teachers you should think about it and learn something.

If not, the comment you got are right: it is a bad algorithm. ;-)

Posted 28-Aug-13 3:09am

KarstenK

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Philippe Mori · Accepted Answer · 2013-08-28T17:04:00

Since you have 2 loops over string A and one over string B, the easy answer would be O(a² * b) where a is the length of first string and b the length of the other string.

In practice, it should be near to O(a * b) for random strings as the sum should not match often in that case.

The worst case would be to search for acd in abeabeacd as the sum will often match but with different letters.

Also the algorithm won't works if duplicate letters are allowed in the shorter word.