In the Aho-Corasick implementation I know you build a trie from the words you search and then construct a set of "failure links". How does this differ from the solution you propose?mf wrote:You can solve it, using a trie data structure to keep the words.
That's simpler to implement than Aho-Corasick.
Ah, OK, I thought that you meant a simpler way to achieve a time complexity comparable to Aho-Corasickmf wrote:In my solution I only need the trie itself. I don't have to compute failure links.
For each starting cell and for each of the eight possible directions, I traverse the trie from the root, spelling out the corresponding string of letters. If some visited vertex represent the last character of a word, I increment the counter for that word.
My solution runs in O(n^3) time per query (where n=max(N,M)).
Code: Select all
#include <cassert>
#include <cstdio>
#include <cstring>
using namespace std;
int main( void ) {
int T, D, Q, M, N;
char buff[10000];
scanf( "%d", &T );
for( int tt = 0; tt < T; ++tt ) {
scanf( "%d", &D );
for( int dd = 0; dd < D; ++dd )
scanf( "%s", buff );
scanf( "%d", &Q );
for( int qq = 0; qq < Q; ++qq ) {
scanf( "%d%d", &M, &N );
for( int mm = 0; mm < M; ++mm ) {
scanf( "%s", buff );
assert( strlen( buff ) == N );
}
}
}
return 0;
}
Code: Select all
cin>>cases;
for(ks=1;ks<=cases;ks++)
{
cin>>d;
for(i=1;i<=d;i++)
{
cin>>W;
if(W.size()<=100) //<---- this is important. without it u will get RTE. i dont know why!
{
}
}
cin>>Q;
for(q=1;q<=Q;q++)
{
cin>>R>>C;
for(i=0;i<R;i++)
for(j=0;j<C;j++)
cin>>board[i][j];
}
}
}Code: Select all
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <queue>
using namespace std;
int counter[15000];
string dict[15000];
struct letter
{
letter *fail,*next[27];
set<int> s;
};
void free (letter *_l)
{
for(int i=0; i<26; i++)
if(_l->next[i]!=NULL )
free(_l->next[i]);
delete[]_l;
}
int main()
{
int tests,d,queries,m,n;
char str[1001];
string s,words[100],w;
letter l,*tmp,*x;
set<int> in;
queue<letter*> q;
s.reserve(100);
for(int i=0; i<15000; i++)
dict[i].reserve(1000);
for(int i=0; i<100; i++)
words[i].reserve(100);
w.reserve(400000);
scanf("%d",&tests);
for(int t=1; t<=tests; t++)
{
l.fail=NULL;
for(int i=0; i<26; i++)
l.next[i]=NULL;
l.next[26]=&l;
l.s.clear();
printf("Test Case #%d\n",t);
scanf("%d",&d);
getchar();
for(int i=0; i<d; i++)
{
fgets(str,sizeof(str),stdin);
str[strlen(str)-1]=0;
if(strlen(str)<101)
{
dict[i]=string(str);
counter[i]=0;
}
else
{
d--;
i--;
}
}
// tworzenie drzewa Trie
for(int i=0; i<d; i++)
{
tmp=&l;
for(unsigned int j=0; j<dict[i].size(); j++)
{
if(tmp->next[dict[i][j]-97]==NULL)
{
tmp->next[dict[i][j]-97]=new letter[1];
tmp=tmp->next[dict[i][j]-97];
for(int j=0; j<26; j++)
tmp->next[j]=NULL;
tmp->next[26]=&l;
}
else
tmp=tmp->next[dict[i][j]-97];
}
tmp->s.insert(i);
}
// uzupelnianie fail przejsc (skroty na drzewie)
for(int i=0; i<26; i++)
if(l.next[i]!=NULL)
{
l.next[i]->fail=&l;
q.push(l.next[i]);
}
else
l.next[i]=&l;
while(!q.empty())
{
tmp=q.front();
q.pop();
for(int i=0; i<26; i++)
if(tmp->next[i]!=NULL)
{
q.push(tmp->next[i]);
x=tmp->fail;
while(x->next[i]==NULL)
x=x->fail;
x=x->next[i];
tmp->next[i]->fail=x;
tmp->s.insert(x->s.begin(),x->s.end());
}
}
scanf("%d",&queries);
for(int c_queries=1; c_queries<=queries; c_queries++)
{
printf("Query #%d\n",c_queries);
w="";
scanf("%d %d",&m,&n);
getchar();
// konwersja tabeli na 1 dlugi napis
for(int i=0; i<m; i++) // wczytywanie + poziomo
{
fgets(str,sizeof(str),stdin);
str[strlen(str)-1]=0;
words[i]=string(str);
w+=words[i]+'{';
}
for(int i=0; i<n; i++) // pionowo
{
s="";
for(int j=0; j<m; j++)
s+=words[j][i];
w+=s+'{';
}
for(int i=m-1; i>0; i--) // na ukos \ (w pionie)
{
s="";
for(int j=0; i+j<m && j<n; j++)
s+=words[i+j][j];
w+=s+'{';
}
for(int i=0; i<n; i++) // na ukos \ (w poziomie)
{
s="";
for(int j=0; i+j<n && j<m; j++)
s+=words[j][i+j];
w+=s+'{';
}
for(int i=m-1; i>0; i--) // na ukos / (w pionie)
{
s="";
for(int j=0; i+j<m && j<n; j++)
s+=words[i+j][n-1-j];
w+=s+'{';
}
for(int i=n-1; i>=0; i--) // na ukos / (w poziomie)
{
s="";
for(int j=0; i-j>=0 && j<m; j++)
s+=words[j][i-j];
w+=s+'{';
}
// wyszkiwanie wzorcow
tmp=&l;
for(unsigned int i=0; i<w.size(); i++)
{
n=w[i]-97;
while(tmp->next[n]==NULL)
tmp=tmp->fail;
tmp=tmp->next[n];
for(set<int>::iterator it=tmp->s.begin(); it!=tmp->s.end(); it++)
{
counter[*it]++;
in.insert(*it);
}
}
tmp=&l;
for(int i=w.size()-1; i>=0; i--)
{
n=w[i]-97;
while(tmp->next[n]==NULL)
tmp=tmp->fail;
tmp=tmp->next[n];
for(set<int>::iterator it=tmp->s.begin(); it!=tmp->s.end(); it++)
{
counter[*it]++;
in.insert(*it);
}
}
for(set<int>::iterator it=in.begin(); it!=in.end(); it++)
//printf("%s %d\n",dict[*it].c_str(),counter[*it]);
cout<<dict[*it]<<' '<<counter[*it]<<endl;
in.clear();
}
for(int i=0; i<26; i++)
if(l.next[i]!=NULL)
{
if(l.next[i]!=&l)
free(l.next[i]);
l.next[i]=NULL;
}
printf("\n");
}
}
