POJ 3691 [Aho-corasick]

gistfile1.cpp

#include <iostream>
#include <sstream>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <numeric>
#include <list>
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define mp make_pair
#define debug( x ) cout << #x << " = " << x << endl
#define clr(v,x) memset( v, x , sizeof v )
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define f(i,a,b) for(int i = a ; i < b ; i++)
#define fd(i,a,b) for(int i = a ; i >= b ; i--)
#define PI acos( -1.0 )
#define EPS 1E-9
#define TAM 1010

using namespace std;

typedef pair<int,int> ii ;
typedef long long ll ;
typedef long double ld ;
typedef pair<int,ii> pii ;

int fail[ TAM ] ;
int sig[ TAM ][ 30 ] ;
ll final[ TAM ] ;
int end ;
string cs = "ACGT" ;
int dp[ TAM ][ TAM ] ;
char word[ TAM ] ;
int len ;

void init(){
	end = 1 ;
	final[ 0 ] = 0 ;
	clr( sig[ 0 ] , 0 ) ;
	fail[ 0 ] = 0 ;
}

void add( string s , int idx ){
	int len = s.size() ;
	int nodo = 0 ;
	f( i , 0 , len ){
		int c = s[ i ] - 'A' ;
		if( !sig[ nodo ][ c ] ){
			clr( sig[ end ] , 0 ) ;
			final[ end ] = 0 ;
			sig[ nodo ][ c ] = end++ ;
		}
		nodo = sig[ nodo ][ c ] ;
	}
	final[ nodo ] |= (1ll<<idx) ;
}

void build(){
	queue<int> q ;
	f( i , 0 , 30 ){
		int next = sig[ 0 ][ i ] ;
		if( next ){
			fail[ next ] = 0 ;
			q.push( next ) ;
		}
	}
	while( !q.empty() ){
		int nodo = q.front() ; q.pop() ;
		f( i , 0 , 30 ){
			int next = sig[ nodo ][ i ] ;
			int rev = sig[ fail[ nodo ] ][ i ] ;
			if( !next ) sig[ nodo ][ i ] = rev ;
			else{
				q.push( next ) ;
				fail[ next ] = rev ;
				final[ next ] |= final[ rev ] ;
			}
		}
	}
}

int go( int nodo , char c ){
	int x = c - 'A' ;
	while( nodo != 0 && !sig[ nodo ][ x ] ) nodo = fail[ nodo ] ;
	return sig[ nodo ][ x ] ;
}

int calc( int idx , int nodo ){
	int & resp = dp[ idx ][ nodo ] ;
	if( resp != -1 ) return resp ;
	if( idx == len ) return 0 ;

	resp = 1<<30 ;
	f( i , 0 , 4 ){
		int next = go( nodo , cs[ i ] ) ;
		if( final[ next ] ) continue ;
		resp = min( resp , calc( idx + 1 , next ) + ( cs[ i ] != word[ idx ] ) ) ;
	}
	return resp ;
}

int main(){

	int n , test = 1 ;
	while( scanf("%d" , &n ) == 1 ){
		if( n == 0 ) break ;
		init() ;
		f( i , 0 , n ){
			scanf("%s" , word ) ;
			add( word , i ) ;
		}
		scanf("%s" , word ) ;
		build() ;
		clr( dp , -1 ) ;
		len = strlen( word ) ;
		int R = calc( 0 , 0 ) ;
		if( R == 1<<30 ) R = -1 ;
		printf("Case %d: %d\n" , test++ , R ) ;
	}
    return 0 ;
}