902 - Password Search

[kenneth]

hint: I solved it using O(n*k) algorithm.

Care to share your method?

[emotional blind]

hint: I solved it using O(n*k) algorithm.

Care to share your method?

try to implement a TRIE.

[coze]

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]

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]

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...

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]

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

[lnr]

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

[lnr]

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

[MRH]

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

Thanks in advance

[LegaNuno]

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

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]

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]

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]

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

Thanks.

[brianfry713]

gr81, don't read line by line on 902, you can change your loop to while(cin >> plen >> str) and get AC.

[MPC1984]

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!