OJ Board

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); // <-- !!!
  }
}

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;
}

Code: Select all

Code Removed after AC

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;                      
}

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;
}

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;

Code: Select all

AC