работа со строками.олимпиадная задача.

[Александра89]

помогите пожалуйста.нужно решение этой задачи на завтра..на языке паскаль или си.
очень,очень нужно..

[Rififi]

Александра89

очень,очень нужно..

Зачем тебе? на чужих мозгах далеко не уедешь :D

вот по-приколу на C++, надеюсь ты всех сразишь ((((((Ж

#include <iostream>
#include <locale>

#include <string>
#include <set>
#include <functional>

bool good(const std::string& s)
{
	std::set<char> unique;
	for (std::string::const_iterator it = s.begin(); it != s.end(); ++it)
	{
		unique.insert(*it);
		if (unique.size() > 2)
			return false;
	}

	return true;
}

template <typename T>
struct size_less : public std::binary_function<T, T, bool>
{
	bool operator()(const T& v1, const T& v2) const
	{ return v1.size() < v2.size(); }
};

std::string find(const std::string& s)
{
	if (s.size() == 1)
		return s;

	std::set<std::string, size_less<std::string> > v;

	for (size_t i=0; i<s.size(); i++)
	for (size_t j=i+1; j<s.size(); j++)
	{
		const std::string sub = s.substr(i, j-i+1);
		if (good(sub))
			v.insert(sub);
	}

	return *v.rbegin();
}

int main()
{
	setlocale(LC_ALL, "");

	const std::string s = "arrdeddsrdsreewdrdcegt";
	std::cout << s << " => " << find(s) << std::endl;

	return 0;
}

Пример работы: http://codepad.org/EZtGOBxM

[Александра89]

спасибо огромное =)
да я не собираюсь уезжать на чужих мозгах..просто вот нужно очень....именно на завтра...для тестирования формального

[Александра89]

мне это просто для формальности нужно.а как переделать тут чтоб строка не константой задавалась,а читалась из файла,как приведено в примере и выводилось так же в файл.просто мне на утро нужно уже..в 10 часов отправить нужно,а сообщили об этом только сейчас(((вот я и сижу..не знаю что и делать..и если вы поможете,то на век останетесь моим спасителем....век буду благодарна вам

[AlexanderKs]

Интересно. Попробую на Pascal

[Rififi]

Александра89

для формальности нужно

Ну тогда и не парься, скажешь им, типа, чё вы тут мне пургу гоните, я и так уже вам весь алгоритм забацала, так что отстаньте от меня со своими дурацкими файлами! :E

... и если вы поможете ...

Я сегодня уже помог бабуле перейти через улицу, а у меня есть правило - не переусердствовать с добрыми делами, а то могу перестать себя контролировать. А ну как начну добро причинять налево-направо, пользу наносить да ласкам подвергать! (с)

[Александра89]

Сообщение от Rififi

Александра89

для формальности нужно

Ну тогда и не парься, скажешь им, типа, чё вы тут мне пургу гоните, я и так уже вам весь алгоритм забацала, так что отстаньте от меня со своими дурацкими файлами! :E

... и если вы поможете ...

Я сегодня уже помог бабуле перейти через улицу, а у меня есть правило - не переусердствовать с добрыми делами, а то могу перестать себя контролировать. А ну как начну добро причинять налево-направо, пользу наносить да ласкам подвергать! (с)

да понимаете...просто навалили на меня и всё...так то сейчас других дел полно..но просто хочется это сделать...не ради кого то и чего то..а ради того что может за то что не проигнорирую это,а сдам всёдаки..отправлю для формальности,может хоть какой то плюсик мне будет,какая нибудь галочка....

фактически меня это не заставляют делать..но мне вот просто хотелось немножко так выделиться...заинтересованность показать и не безразличие....поэтому и прошу,тем более если передо мной люди знающие,для которых это займёт не более 5 минут..

[Son Of Pain]

вот по-приколу на C++, надеюсь ты всех сразишь ((((((

Этому коду явно не хватает лямбда-функций высокого порядка, с ними он стал бы в два раза короче

[val_nnm]

Ни если уж совсем для формальности. Вот на паскале полный вариант.

function GetMaxStringLengthForPos(const s:string;startPos:integer; endPos:integer):integer;
var c:array[1..2] of char;
    n,i:integer;
    pos:integer;
    
Begin
  GetMaxStringLengthForPos := 0;
  n := 0;
  pos := startPos;
  while (pos <= endPos) do
  Begin
    i := 1;
    while (i<=n) do Begin
      if (c[i]=s[pos]) then break;
      i := i+1;
    end;
    if (i>=3) then Begin
      break;
    end else
      GetMaxStringLengthForPos := pos-startPos+1;
    c[i] := s[pos];
    if (n<i) then n := i;
    pos := pos+1;
  end;
End;

var l:integer;
    maxLength:integer;
    maxPos:integer;
    s:string;
    i:integer;
    tempLength:integer;
    c:char;
    inputFile:text;
    outputFile:text;

Begin
  assign(inputFile,'input.txt');
  reset(inputFile);
  s := '';
  readln(inputFile,l);
  for i := 1 to l do Begin
    read(inputFile,c);
    s := s+c;
  end;
  close(inputFile);
  maxPos := 0;
  maxLength := 0;
  l := Length(s);
  for i := 1 to l do Begin
    tempLength := GetMaxStringLengthForPos(s,i,l);
    if (tempLength>=maxLength) then Begin
      maxLength := tempLength;
      maxPos := i;
    end;
  end;

  assign(outputFile,'output.txt');
  rewrite(outputFile);
  writeln(outputFile,copy(s,maxPos,maxLength));
  close(outputFile);  
End.

Вот кстати придумал другой вариант. (намного быстрее первого, и тянет на очень неплохую оценку)
Програма расматривает окно от pStart до pEnd на этом участке подсчитывает колличество каждого вида, и количество видов сиволов. Есл количесво разных символов меньше или равно 2 то двигает pEnd, если больше 2 то двигает pStart. (врямя выполнения прамо пропорционально количеству символов (n), в отличии от прошлого где время проорционально его квадрату (n*n))

const MaxDifrentChars = 2;
function GetMaxString(const s:string;startPos:integer; endPos:integer):string;
var c:array[1..MaxDifrentChars+1] of char;
    c_count:array[1..MaxDifrentChars+1] of integer;
    n,i:integer;
    pStart:integer;
    pEnd:integer;

    maxLength:integer;
    maxPos:integer;    
Begin
  for i := 1 to MaxDifrentChars+1 do c_count[i] := 0;

  n := 0;
  maxLength := 0;
  maxPos := 1;    

  pStart := startPos;
  pEnd := startPos;
  while ((pEnd <= endPos)or(n>MaxDifrentChars)) do
  Begin
    if (n<=MaxDifrentChars) then Begin
      i := 1;
      while (i<=MaxDifrentChars+1) do Begin
        if (c_count[i]>0) and (c[i]=s[pEnd]) then begin
          c_count[i] := c_count[i]+1;
          break;
        end;
        i := i+1;
      end;
      if (i>MaxDifrentChars+1) then Begin
        i := 1;
        while (i<=MaxDifrentChars+1) do Begin
          if (c_count[i]=0) then begin
            c_count[i] := 1;
            c[i] := s[pEnd];
            n := n+1;
            break;
          end;
          i := i+1;
        end;
      end;
      pEnd := pEnd+1;
    end else Begin
      i := 1;
      while (i<=MaxDifrentChars+1) do Begin
        if (c_count[i]>0) and (c[i]=s[pStart]) then begin
          c_count[i] := c_count[i]-1;
          if (c_count[i]=0) then Begin
            n := n - 1;
          end;
          break;
        end;
        i := i+1;
      end;
      pStart := pStart+1;
    end;

    if (n<=MaxDifrentChars) then
      if (pEnd-pStart>=maxLength) then Begin
        maxLength := pEnd-pStart;
        maxPos := pStart;
      end;
  end;
  GetMaxString := copy(s,maxPos,maxLength);
End;

var l:integer;
    s:string;
    i:integer;
    c:char;
    inputFile:text;
    outputFile:text;

Begin
  assign(inputFile,'input.txt');
  reset(inputFile);
  s := '';
  readln(inputFile,l);
  for i := 1 to l do Begin
    read(inputFile,c);
    s := s+c;
  end;
  close(inputFile);

  assign(outputFile,'output.txt');
  rewrite(outputFile);
  writeln(outputFile,GetMaxString(s,1,Length(s)));
  close(outputFile);  
End.

p.s. просьба к Александра89 раскажите как сдадите, и с каким результатом?

[AlexanderKs]

Пришли мысли.. Выбрал самую интересную.

program Project;
uses crt;
var
  txt:Text;
  str,s:string; // str - подстроки, кот. вытаскиваем из прочит. строки s
  i,n,a,len,st:byte;//i-цикл, n-длина строки, a-начало найд. подстроки,
                        // len-длина подстроки, st-начало самой длин. подстр.
begin
   Assign(txt,'input.txt');
   Reset(txt);
   Readln(txt,n);
   Readln(txt,s);
   Close(txt);
   
   str:=s[1]+s[2]; // сначала берем 2 перв. симв. строки
   a:=1;
   i:=3;
   st:=1;
   len:=0;
   while i<=n+1 do begin // n+1 чтобы последн. подстрока тоже проанализ.
     if (pos(s[i],str)>0) and (i<=n) then begin
       str:=str+s[i];
       inc(i);
     end else begin
       if len<=length(str) then begin
	 len:=Length(str);
	 st:=a;
       end;
       inc(a);
       str:=s[a]+s[a+1];
       i:=a+2;
     end;
   end;
   Assign(txt,'output.txt');
   Rewrite(txt);
   WriteLn(txt,copy(s,st,len));
   Close(txt);
end.