Kod: Zaznacz cały
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string lines[ 10000 ] , bitek = "bitek" , wymazany;
int n;
vector< int >poz , poz2;
int ZnajdzLitere( int line , char litera )
{
for( int i = poz[ line ] ; i < lines[ line ].size() ; i++ )
{
if( lines[ line ][ i ] == litera )
return i;
}
return -1;
}
char ZnajdzNajlepsza()
{
int j , i , temp;
for( i = 25 ; i >= 0 ; i-- )
{
for( j = 0 ; j < n ; j++ )
{
temp = ZnajdzLitere( j , 'a' + i );
if( temp != -1 )
poz2[ j ] = temp + 1;
else
break;
}
if( j == n )
{
poz = poz2;
return i + 'a';
}
}
return -1;
}
int main()
{
ios_base::sync_with_stdio( 0 );
bool ok = true , wiekszy = false;
cin >> n;
poz.resize( n );
poz2.resize( n );
for( int i = 0 ; i < n ; i++ )
cin >> lines[ i ];
while( true )
{
char temp = ZnajdzNajlepsza();
if( temp != -1 )
{
wymazany += temp;
if( wymazany.size() <= bitek.size() && !wiekszy )
{
if( wymazany[ wymazany.size() - 1 ] < bitek[ wymazany.size() - 1 ] )
{
cout << "bitek";
ok = false;
break;
}
if( wymazany[ wymazany.size() - 1 ] > bitek[ wymazany.size() - 1 ] )
wiekszy = true;
}
}
else
break;
}
if( ok )
cout << wymazany;
return 0;
}
Wyczytałem na pewnej stronie, że należy zastosować "Malejący ciąg maksimów globalnych". Nie wiem niestety jak to tu wykorzystać. Może ma ktoś jakiś pomysł?