файл без пустых и повторяющихся строк.
как узнть повтор?
int n = StringCount;
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
if(строка с инексом i равна строке с инексом j) ...
}
}
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
{
if(строка с инексом i равна строке с инексом j) ...
}
}
это жутко долго будет работать - O(n^2 * length).
можно строить бор из строк и для каждой последующей проверять там наличие. сложность - O(n * length)
P.S Если непонятно - могу написать подробнее.
можно строить бор из строк и для каждой последующей проверять там наличие. сложность - O(n * length)
P.S Если непонятно - могу написать подробнее.
Зато это тут особо думать не нужно :о)
Если это, скажем, лаба по инфе, то фиг бы, что долго, зато человек, если его спросят, сможет легко разобраться.
Впрочем это скорее решение с точки зрения олимпиадного программирования - на время работы есть серьёзные ограничения.
Впрочем это скорее решение с точки зрения олимпиадного программирования - на время работы есть серьёзные ограничения.
а можно код предоставить? чтобы быстро все было... очень заинтересовало ;)
PS: этот код работает только с Ansi? или с Wide тоже будет работать...
[highlight=bash]
cat file | uniq | egrep -v ^$
[/highlight]
посложнее
[highlight=perl]
my $hash = {};
$hash->{$_}++ while (<>);
for (keys %$hash) { chomp; print if $_; }
[/highlight]
а почему сразу не написать, что на С++ ;)
я в С++ не силен, но если что - наши гуру поправят.
[highlight=C++]
#include <map>
#include <string>
#include <iostream>
int main() {
std::map <std::string,int> hash;
std::string str;
while( std::cin >> str ) hash[str]++;
std::map<std::string,int>::iterator i;
for( i = hash.begin(); i != hash.end(); i++ ) {
if ( i->first != "")
std::cout << i->first << std::endl;
}
return 0;
}
[/highlight]
обращаю внимание - программа работает не с файлом, а с входным потоком данных, т. е. данные можно как вводить с клавиатуры, так и подавать через каналы на вход.
PS: этот код работает только с Ansi? или с Wide тоже будет работать...
[highlight=c++]
#include <stdio.h>
#define nil -1
int next = 0;
int children[1000][255];
bool isEnd[1000];
bool addString(int b, char* str) {
if (str[0]==0) {
if (isEnd) return false;
isEnd = true;
return true;
}
if (chidren[str[0]]==nil) {
chidren[str[0]] = next;
for (int a=0;a<255;a++) children[next][a] = nil;
isEnd = false;
next++;
}
return addString(children[str[0]], str+1);
}
int main() {
for (int a=0;a<255;a++) children[next][a] = nil;
isEnd = false;
next++;
while (true) {
char* str;
scanf("%s", &str);
if (addString(0, str)) printf("%s\n", str);
}
}
[/highlight]
Не уверен что работает - не тестировал.
Сложность алгоритма - O(n*length* c) (c - размер алфавита)
Вариант squirL работает, как мне кажется, за O(n*log(n) * length)