902 - Password Search

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by kenneth » Tue Mar 25, 2008 7:17 am

emotional blind wrote:hint: I solved it using O(n*k) algorithm.
Care to share your method?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Mar 26, 2008 5:43 am

kenneth wrote:
emotional blind wrote:hint: I solved it using O(n*k) algorithm.
Care to share your method?
try to implement a TRIE.

coze
New poster
Posts: 26
Joined: Tue Nov 27, 2007 7:56 am
Location: Japan

Re: 902 Password Search

Post by coze » Wed Apr 16, 2008 3:20 am

This code gets Runtime error. Why?

Code: Select all

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

const int N = 3000000;
char s[N];
int n_;

bool compare(const char* a, const char* b) {
  return strncmp(a, b, n_) <= 0;
}

int main() {
  int n;
  while (2 == scanf("%d %s", &n, &s[0])) {
    int len = strlen(s);
    n_ = n;
    assert(n < len);

    vector<char*> v;
    int m = len - n;
    for (int i = 0; i <= m; i++)
      v.push_back(s + i);

    sort(v.begin(), v.end(), compare); // <-- !!!
  }
}

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

Re: 902 - Password Search

Post by alamgir kabir » Sat Apr 18, 2009 10:14 pm

Please help me. I am getting RE a huge number of time but I didn't find any fault in my code. I am reading all the post here

Code: Select all

#include<stdio.h>
#include<string>
#include<vector>
#include<iostream>
#include <stdlib.h>
#include "alloc.h"
using namespace std;

char str [ 10000000 ], *tok, s [ 10000000 ], password [ 10000000 ];


struct Trie
{
    int word, prefix;
    struct Trie* edges [ 27 ];
};

void init( struct Trie **node )
{
    *node = (Trie*) malloc( sizeof( struct Trie ) );

    (*node) -> word = 0;
    (*node) -> prefix = 0;

    for( int i = 0; i < 26; i ++)
    {
        (*node) -> edges [ i ] = NULL;
    }
    return;
}


bool is_empty( char *str )
{
    return strlen( str ) <= 0;
}

void add_word( struct Trie **node , char *str, int i )
{
    int k = str [ 0 ] - 'a';

    if( is_empty( str ) )
    {
        (*node) -> word = (*node) -> word + 1;
        return;
    }
    else
    {
        ((*node) -> prefix) = ((*node) -> prefix) + 1;

        if( ( *node ) -> edges [ k ] == NULL ) init( &(( *node ) -> edges [ k ] ));

        add_word( &(*node) -> edges [ k ], &str [ i ], i ++ );
    }
}
int count_words( struct Trie *node , char *str, int i )
{
    int k = str [ 0 ] - 'a';
    if( is_empty( str ) ) return node -> word;
    else  if( node -> edges [ k ] == NULL ) return 0;
    else return count_words( node -> edges [ k ], &str [ i ], i ++ );

}


int main()
{
    //freopen("input.txt", "r", stdin);
    int num, i, j, len, count, max;
    Trie *t;

    while( gets( str ) )
    {
        init( &t );
        max = 0;

        tok = strtok( str , " ");
        sscanf(tok, "%d", &num);
        tok = strtok( NULL , " ");
        sscanf(tok, "%s", str);
        //printf("%d %s\n", num, str);
        len = strlen( str );
        for( i = 0; i <= len - num; i ++ )
        {
            for( j = 0; j < num; j ++ )
            {
                s [ j ] = str [ i + j ];
            }
            s [ j ] = '\0';

            add_word(&t, s, 0);
            count = count_words( t, s, 0 );

            //printf("%s %d\n", s, count);

            if( max < count)
            {
                max = count;
                strcpy( password, s);
            }
        }
        printf("%s\n", password);

    }
    return 0;
}



Thanks in advance

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 902 - Password Search

Post by mf » Sun Apr 19, 2009 1:44 am

Perhaps, it has to do something with the fact that you don't free allocated memory?
You know, C++ doesn't have automatic garbage collection...

coze wrote:This code gets Runtime error. Why?
...
bool compare(const char* a, const char* b) {
return strncmp(a, b, n_) <= 0;
}
...
sort(v.begin(), v.end(), compare); // <-- !!!
RTFM:
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/StrictWeakOrdering.html

shankhs
New poster
Posts: 3
Joined: Tue May 20, 2008 4:10 am

Re: 902 - Password Search

Post by shankhs » Mon Jun 22, 2009 9:52 pm

Why I am getting TLE?
I read in the previous posts that somebody got AC using map and substr , I have used only these things but still getting TLE!!!

Code: Select all

Code Removed after AC

User avatar
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 902 - Password Search

Post by lnr » Sat Jun 12, 2010 3:41 pm

Now i'm getting wrong answer.
Can anyone post some input output?

User avatar
lnr
Experienced poster
Posts: 141
Joined: Sat Jun 30, 2007 2:52 pm
Location: Dhaka,Bangladesh

Re: 902 - Password Search

Post by lnr » Sat Jun 12, 2010 7:15 pm

Accepted.
A little mistake.
i<=(l-N) would be i<(l-N) and got ACC.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 902 - Password Search

Post by MRH » Sun Jun 27, 2010 3:43 am

I try to sloved this problem using Trie but it Wong answer.
Please give me some critical case

Thanks in advance

LegaNuno
New poster
Posts: 1
Joined: Mon May 02, 2011 7:08 pm

getting RE on 902 - Password Search

Post by LegaNuno » Wed May 04, 2011 6:26 pm

So as you can see my probelm is that i have no ideia why this is getting me RE, i can compile it as normal and run it too :cry:
Your submission with number 8810000 for the problem 902 - Password Search has failed with verdict Runtime error.

This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0.

Code: Select all

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void string_procura(char str[],int n) 
{
     char **ptr=NULL;
     int size=0,i=0,j=0,cont=0,total=0,pos=0;
     size=(strlen(str)-n+1);
     ptr=malloc(sizeof(char)*size);
     for (i=0;i<size;i++)
        {
           ptr[i]=malloc(sizeof(char)*n);
           strncpy(ptr[i],&str[i],n);
           for (j=i;j<size;j++)
               {
                 if (i!=j)
                    {
                      if (strncmp(ptr[i],&str[j],n)==0)
                         {
                          cont++;
                          if (cont>total)
                             {
                               total=cont;
                               pos=i;
                              }
                         }
                    }
               }
         }
     if (total>0)
        {
         printf("%s",ptr[pos]);
         for(i=0;i<size;i++)
           free(ptr[i]);
         free(ptr);
        }
}

int main()                          
{                                      
    char str[100];                   
    int n=0;                        
    printf("Introduza o valor: ");  
    scanf("%d",&n);                 
    printf("Introduza a frase :");  
    scanf("%s",str);                
    string_procura(str,n);      
    return 0;                      
}

receme
New poster
Posts: 17
Joined: Thu Jul 01, 2010 11:55 am

Re: 902 - Password Search

Post by receme » Sat Jun 18, 2011 11:29 pm

I got ac... my process is...
I find every sub string by using substr() function and use a map to count the frequency of those substring. just like this.

map<string,int>mp;
string b=input.substr(address,length);

mp++;

then I found the max frequncy simply by linear search. But, by this process.....
input:
2 ababa
2 babab

both the ouput i got is ab. And I got ac. But I think the output of second case should be "ba".

I solved this problem using this approch long time ago..but I didn't submit my code consider this test cases. Today I submit and got AC.

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 902 - Password Search

Post by sir. manuel » Sun Oct 16, 2011 10:40 pm

Why WA??????

Code: Select all

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<cmath>
#include<string>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<utility>
#include<list>
#include<set>
#include<map>
using namespace std;
string s;

int main(){
  string auxi;  int tam; map<string,int>mapa;
  while(getline(cin,auxi)){
  stringstream flujos(auxi);
  flujos>>tam;  flujos>>s;  int l=s.size();
  int maximo=0; string sol,cadena;
    for(int i=0;i<l-tam+1;i++){
      sol="";
	 sol=s.substr(i,tam);
      mapa[sol]++;
    }
   map<string,int>::iterator it=mapa.begin();
    while(it!=mapa.end()){
   if( (*it).second > maximo){
	   maximo=(*it).second;
	  cadena=(*it).first;
	 }
   it++;
   }
    
mapa.clear(); 
  cout<<cadena<<endl;
  }
  return 0;
}
too i tried with ...

Code: Select all

for(int i=0;i<l-tam+1;i++){
      sol="";
	 sol=s.substr(i,tam);
       int as=++mapa[sol];
    if( as > maximo){
	   maximo=as;
	   cadena=sol;
	 }
    }
    
mapa.clear(); 
  cout<<cadena<<endl;



gr81
New poster
Posts: 46
Joined: Wed Sep 26, 2012 7:52 pm

Re: 902 - Password Search

Post by gr81 » Sat Feb 09, 2013 7:59 pm

getting WA , plz help , code is at http://ideone.com/5P3YzZ

Thanks.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 902 - Password Search

Post by brianfry713 » Mon Feb 11, 2013 10:25 pm

gr81, don't read line by line on 902, you can change your loop to while(cin >> plen >> str) and get AC.
Check input and AC output for thousands of problems on uDebug!

MPC1984
New poster
Posts: 40
Joined: Mon Jul 01, 2013 9:24 pm
Location: Valladolid, Spain

Re: 902 - Password Search

Post by MPC1984 » Wed Sep 11, 2013 7:21 pm

Hi everybody!
Can anybody help me with this problem?
I don't know why I got RTE with this code:

Code: Select all

AC
Thanks in advance! :wink:
Last edited by MPC1984 on Thu Sep 12, 2013 1:28 pm, edited 1 time in total.

Post Reply

Return to “Volume 9 (900-999)”