Программа не улаживается во время!

[sergey123]

Здравствуйте. Я решаю одну олимпиадную задачу,и она должна улаживатся в 2 секунды. Можете помочь мне оптимизировать программу?

#include <iostream>
#include <string>
using namespace std;
int sum=0;
int n;



int P(string a,string b){
         int pos=0,k;
           int i,j;
   i=0;j=n-1;
         pos= a.find(b);
         if(pos!=-1)return 1; 
           for(;;){
          if(i>=j)return 0;
          if(a[i]!=a[j])return 1;
          i++;j--;
}
}
 int F(string a,string b){
     
     int k;
     if(a.length()==n)
     {k=P(a,b);if(k==0){sum++;}return 0;}

         F(a+'A',b);
         F(a+'B',b);
         return 0; 
   }
   

int main()
{
   
  string a,b;   
    cin>>b>>n;
F(a,b);
cout<<sum;
//system("PAUSE");
     return 0;
}

Условие задачи:Известно, что палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, палиндромами являются строки “A”, “ABA”, “ABBA”, а строки “AB”, “AAB”, “ABAB” палиндромами не являются. В новогоднюю ночь роботы генерировали пожелания друг другу в виде палиндромов. Но чтобы пожелание было добрым оно не должно содержать запрещенных строк. Рассмотрим некоторую строку S, состоящую только из латинских букв A и B. Назовем запрещенными все строки длины N, которые состоят также только из букв A и B и содержат S в качестве подстроки. Например, если S = “AB” и N = 3, то существует четыре запрещенных строки: “AAB”, “ABA”, “ABB” и “BAB”. Остальные строки будет называть допустимыми.

Помогите роботам с генерацией добрых пожеланий - напишите программу, которая для заданной строки S длиной не более пяти символов и заданного числа N определяет количество допустимых строк длины N, которые являются палиндромами.
Формат входных данных
Первая строка содержит строку S. Вторая строка содержит одно целое число N. Длина строки S не превосходит пяти.

1 ≤ N ≤ 100
Формат выходных данных
Выведите одно целое число - количество строк длины N, которые являются палиндромами и не содержат S в качестве подстроки.

[BDA]

#include <iostream>
#include <string>
 
using namespace std;
 
int p(string a, string s, int n)
{
    if(a.length() == n)
        if (a.find(s) != -1)
            return 0;
        else
            return 1;
    return (p("A" + a + "A", s, n) + p("B" + a + "B", s, n));
}
 
 
int main()
{
    string s = "";
    int n = 0;
    cin >> s >> n;
    if (n%2)
        cout << (p("A", s, n) + p("B", s, n));
    else
        cout << p("", s, n);
    return 0;
}

Предварительное ускорение.
На тесте AAB 20 Ваша программа работает 0.52 секунды, моя - 0.01.
Но тест с N, равным 100, моя программа выполняет дольше 5 секунд (на ideone.com ограничение в 5 секунд на исполнение).
Также, не могу гарантировать, что программа (моя) вообще правильно работает (мысли-то о НГ)

[sergey123]

Спасибо. Ваша программа намного лучше моей.

[BDA]

Пожалуйста.
Вы ее отправляли? Сколько тестов проходит (из спортивного интереса)?

[sergey123]

Всего 50 тестов. Моя порходила 10 тестов,а ваша 22 теста. Скорей всего надо менять алгоритм решения.

[BDA]

Скорей всего надо менять алгоритм решения.

Да, тоже склоняюсь к такому варианту, но пока ничего в голову не пришло.
А пишется, почему не проходят остальные тесты (или хотя бы на том тесте, что споткнулась)?

Попробуйте такой вариант:

#include <iostream>
#include <string>
 
using namespace std;
 
int p(string a, string s, int n)
{
    if (a.find(s) != -1)
        return 0;
    else if(a.length() == n)
        return 1;
    else
        return (p("A" + a + "A", s, n) + p("B" + a + "B", s, n));
}
 
 
int main()
{
    string s = "";
    int n = 0;
    cin >> s >> n;
    if (n%2)
        cout << (p("A", s, n) + p("B", s, n));
    else
        cout << p("", s, n);
    return 0;
}

[sergey123]

Ваш второй вариант проходит 25 тестов. Все ошбки-это программа не проходит по времени (лимит 2 секунды,а программа работает 2.028-2.012 секунд).Я думаю,что надо вывести формулу типа общее кол-во палиндромов отнять кол-во палиндромов, содержащих в себе строку S.
общее кол-во палиндромов я знаю как найти.Над кол-во палиндромов, содержащих в себе строку S работаю в данный момент.

[BDA]

Идем на радикальные меры и отказываемся от string

#include <iostream>
#include <string.h>
 
using namespace std;
 
int p(char *buf, char *s, int l, int r)
{
    if (strstr(&buf[l + 1], s))
        return 0;
    if (l == -1)
        return 1;
    buf[l] = 'A';
    buf[r] = 'A';
    int sum = p(buf, s, l - 1, r + 1);
    buf[l] = 'B';
    buf[r] = 'B';
    sum += p(buf, s, l - 1, r + 1);
    return sum;
}
 
int main()
{
    int n = 0;
    char s[6];
    cin >> s >> n;
    char buf[n + 1];
    memset(buf, 0, sizeof(buf));
    if (n%2) {
        buf[n/2] = 'A';
        int sum = p(buf, s, n/2 - 1, n/2 + 1);
        memset(buf, 0, sizeof(buf));
        buf[n/2] = 'B';
        sum += p(buf, s, n/2 - 1, n/2 + 1);
        cout << sum;
    } else {
        cout << p(buf, s, n/2 - 1, n/2);
    }
    return 0;
}

Тест: AAB 60
мой 2 вариант 3.93s
этот вариант 2.12s

Над кол-во палиндромов, содержащих в себе строку S работаю в данный момент.

Тоже люблю вывести красивую формулу, но не всегда это легко/возможно сделать.

[sergey123]

На 5 тестов непровильный ответ выводит + ошибка время выполнения много тестов.

[sergey123]

а формулу я практически вывел