1270 Search

[•andrei.12]

Aici puteti discuta despre problema Search.

[•andreiulian]

Va rog mult, e cineva dispus sa se uite pe sursa mea? Are complexitatea celei oficiale, dar se incadreaza foarte prost in timp.


#include<iostream>
#include<fstream>
#include<stack>
#include<cstring>
#define l(a) a-'a'
using namespace std;
ifstream in("9-search.in");
ofstream out("search.out");
int N,M,len[105];
char s[5005],c;
short poz[105][5005][30]; //in cuvantul i incepand cu pozitia j litera a apare pe pozitia
stack<char> st;
stack<int> last[105];
int main()
{

    int i,j,k,r;
    char uc;
    in>>N>>M;
    for(i=1;i<=N;++i)
    {
        in>>s+1;
        len=strlen(s+1);
        for(j=len;j>=0;--j)
        {
            for(c='a';c<='z';++c) poz[j][l(c)]=poz[j+1][l(c)];
            poz[j][l(s[j])]=j;
        }
    }
    for(i=1;i<=N;++i) last.push(0);
    for(k=1;k<=M;++k)
    {
        in>>c;
        if(c=='-')
        {
            st.pop();
            for(i=1;i<=N;++i) last.pop(),last.pop();
        }
        else st.push(c);
        uc=st.top();
        r=0;
        for(i=1;i<=N;++i)
        {
            if(poz[last.top()][l(uc)] && poz[last.top()][l(uc)]<=len)
            {
                ++r;
                last.push(poz[last.top()][l(uc)]+1);
            }
            else last.push(-1);
        }
        out<<r<<'\n';
    }
}

[•Vman]

ifstream in("9-search.in");

short poz[105][5005][30];
..
 poz[j][l(s[j])]=j; // iti lipseste o dimensiune aici

probabil va trebui sa inlocuiesti stack-ul cu ceva mai rapid

[•andreiulian]

multumesc