Oulipo
Problem's Link
----------------------------------------------------------------------------
Mean:
给你一个模式串P和一个母串S,让你统计P串在S串中出现的次数.
analyse:
一开始想到的就是使用KMP,就用KMP写了,93ms,挺快的.
我又用AC自动机写了一遍,万万没想到竟然超时了.
后来看别人有用字符串hash写的,于是又用字符串hash写了一遍,代码30+行,而且速度也挺快,173ms.
字符串hash确实是一个好东西 在字符串hash中又学到了unsigned long long超范围后会自动对2^64取模,省去了手动取模.
Time complexity: O(N+M)
view code
1.字符串hash代码
#include<stdio.h>
#include<string.h>
#define ULL unsigned long long
int seed = 100;
char s1 [ 10005 ], s2 [ 1000005 ];
int main()
{
int t;
scanf( "%d" , & t);
while( t --)
{
scanf( "%s%s" , s1 , s2);
int len1 = strlen( s1 ), len2 = strlen( s2);
ULL a1 = 0 , a2 = 0 , l1 = 1;
for( int i = 0; i < len1; ++ i)
{
a1 = a1 * seed +( s1 [ i ] - 'A' + 1);
l1 *= seed;
}
for( int i = 0; i < len1; ++ i)
{
a2 = a2 * seed +( s2 [ i ] - 'A' + 1);
}
int ans = 0;
if( a1 == a2) ans ++;
for( int i = len1; i < len2; ++ i)
{
a2 = a2 * seed +( s2 [ i ] - 'A' + 1) - l1 *( s2 [ i - len1 ] - 'A' + 1);
if( a2 == a1) ans ++;
}
printf( "%d \n " , ans);
}
return 0;
}
#include<string.h>
#define ULL unsigned long long
int seed = 100;
char s1 [ 10005 ], s2 [ 1000005 ];
int main()
{
int t;
scanf( "%d" , & t);
while( t --)
{
scanf( "%s%s" , s1 , s2);
int len1 = strlen( s1 ), len2 = strlen( s2);
ULL a1 = 0 , a2 = 0 , l1 = 1;
for( int i = 0; i < len1; ++ i)
{
a1 = a1 * seed +( s1 [ i ] - 'A' + 1);
l1 *= seed;
}
for( int i = 0; i < len1; ++ i)
{
a2 = a2 * seed +( s2 [ i ] - 'A' + 1);
}
int ans = 0;
if( a1 == a2) ans ++;
for( int i = len1; i < len2; ++ i)
{
a2 = a2 * seed +( s2 [ i ] - 'A' + 1) - l1 *( s2 [ i - len1 ] - 'A' + 1);
if( a2 == a1) ans ++;
}
printf( "%d \n " , ans);
}
return 0;
}
2.KMP代码
// Memory Time
// 1347K 0MS
// by : Snarl_jsb
// 2014-10-04-11.53
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
char s1 [ 10005 ], s2 [ 1000005 ];
vector < int > next;
void GetNext( char s [])
{
int len = strlen(s ), k = 0;
next . clear();
next . push_back( 0);
for( int i = 1; i < len; ++ i)
{
while( k != 0 &&s [ i ] !=s [ k ])
k = next [ k - 1 ];
if(s [ i ] ==s [ k ])
k ++;
next . push_back( k);
}
}
int KMP( char s1 [], char s2 [])
{
int l1 = strlen( s1 ), l2 = strlen( s2);
int k = 0 , ans = 0;;
for( int i = 0; i < l2; ++ i)
{
while( k != 0 && s2 [ i ] != s1 [ k ])
k = next [ k - 1 ];
if( s2 [ i ] == s1 [ k ])
k ++;
if( k == l1)
{
ans ++;
k = next [ k - 1 ];
}
}
return ans;
}
int main()
{
int t;
scanf( "%d" , & t);
while( t --)
{
scanf( "%s%s" , s1 , s2);
int len1 = strlen( s1 ), len2 = strlen( s2);
GetNext( s1);
printf( "%d \n " , KMP( s1 , s2));
}
return 0;
}
// 1347K 0MS
// by : Snarl_jsb
// 2014-10-04-11.53
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define N 1000010
#define LL long long
using namespace std;
char s1 [ 10005 ], s2 [ 1000005 ];
vector < int > next;
void GetNext( char s [])
{
int len = strlen(s ), k = 0;
next . clear();
next . push_back( 0);
for( int i = 1; i < len; ++ i)
{
while( k != 0 &&s [ i ] !=s [ k ])
k = next [ k - 1 ];
if(s [ i ] ==s [ k ])
k ++;
next . push_back( k);
}
}
int KMP( char s1 [], char s2 [])
{
int l1 = strlen( s1 ), l2 = strlen( s2);
int k = 0 , ans = 0;;
for( int i = 0; i < l2; ++ i)
{
while( k != 0 && s2 [ i ] != s1 [ k ])
k = next [ k - 1 ];
if( s2 [ i ] == s1 [ k ])
k ++;
if( k == l1)
{
ans ++;
k = next [ k - 1 ];
}
}
return ans;
}
int main()
{
int t;
scanf( "%d" , & t);
while( t --)
{
scanf( "%s%s" , s1 , s2);
int len1 = strlen( s1 ), len2 = strlen( s2);
GetNext( s1);
printf( "%d \n " , KMP( s1 , s2));
}
return 0;
}
3.AC自动机(TLE)
/**
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
* Author: crazyacking
* Date : 2016-01-18-23.59
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
const int N = 1001000;
char str [N ];
struct node
{
node * next [ 30 ];
node * fail;
int count;
node()
{
for( int i = 0; i < 30; i ++)
next [ i ] = NULL;
count = 0;
fail = NULL;
}
} * q [N ];
node * root;
int head , tail;
void Insert( char * str)
{
node *p = root;
int i = 0 , index;
while( str [ i ])
{
index = str [ i ] - 65;
if(p -> next [ index ] == NULL)
p -> next [ index ] = new node();
p = p -> next [ index ];
i ++;
}
p -> count ++;
}
void build_ac_automation( node * root)
{
root -> fail = NULL;
q [ tail ++ ] = root;
while( head < tail)
{
node * temp = q [ head ++ ];
node *p = NULL;
for( int i = 0; i < 30; i ++)
{
if( temp -> next [ i ] != NULL)
{
if( temp == root) temp -> next [ i ] -> fail = root;
else
{
p = temp -> fail;
while(p != NULL)
{
if(p -> next [ i ] != NULL)
{
temp -> next [ i ] -> fail = p -> next [ i ];
break;
}
p = p -> fail;
}
if(p == NULL) temp -> next [ i ] -> fail = root;
}
q [ tail ++ ] = temp -> next [ i ];
}
}
}
}
int total = 0;
int Query( node * root)
{
int i = 0 , cnt = 0 , index;
node *p = root;
int idx = 0;
while( str [ i ])
{
index = str [ i ] - 65;
while(p -> next [ index ] == NULL && p != root);
p = p -> fail;
p = p -> next [ index ];
if(p == NULL)
p = root;
node * temp = p;
while( temp != root && temp -> count != - 1)
{
if( temp -> count > 0)
{
cnt ++;
}
temp = temp -> fail;
}
i ++;
}
return cnt;
}
int main()
{
int t;
cin >> t;
while( t --)
{
head = tail = 0;
root = new node();
scanf( "%s" , str);
Insert( str);
build_ac_automation( root);
scanf( "%s" , str);
// Query(root);
printf( "%d \n " , Query( root));
}
return 0;
}
* -----------------------------------------------------------------
* Copyright (c) 2016 crazyacking.All rights reserved.
* -----------------------------------------------------------------
* Author: crazyacking
* Date : 2016-01-18-23.59
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long( LL);
typedef unsigned long long( ULL);
const double eps( 1e-8);
const int N = 1001000;
char str [N ];
struct node
{
node * next [ 30 ];
node * fail;
int count;
node()
{
for( int i = 0; i < 30; i ++)
next [ i ] = NULL;
count = 0;
fail = NULL;
}
} * q [N ];
node * root;
int head , tail;
void Insert( char * str)
{
node *p = root;
int i = 0 , index;
while( str [ i ])
{
index = str [ i ] - 65;
if(p -> next [ index ] == NULL)
p -> next [ index ] = new node();
p = p -> next [ index ];
i ++;
}
p -> count ++;
}
void build_ac_automation( node * root)
{
root -> fail = NULL;
q [ tail ++ ] = root;
while( head < tail)
{
node * temp = q [ head ++ ];
node *p = NULL;
for( int i = 0; i < 30; i ++)
{
if( temp -> next [ i ] != NULL)
{
if( temp == root) temp -> next [ i ] -> fail = root;
else
{
p = temp -> fail;
while(p != NULL)
{
if(p -> next [ i ] != NULL)
{
temp -> next [ i ] -> fail = p -> next [ i ];
break;
}
p = p -> fail;
}
if(p == NULL) temp -> next [ i ] -> fail = root;
}
q [ tail ++ ] = temp -> next [ i ];
}
}
}
}
int total = 0;
int Query( node * root)
{
int i = 0 , cnt = 0 , index;
node *p = root;
int idx = 0;
while( str [ i ])
{
index = str [ i ] - 65;
while(p -> next [ index ] == NULL && p != root);
p = p -> fail;
p = p -> next [ index ];
if(p == NULL)
p = root;
node * temp = p;
while( temp != root && temp -> count != - 1)
{
if( temp -> count > 0)
{
cnt ++;
}
temp = temp -> fail;
}
i ++;
}
return cnt;
}
int main()
{
int t;
cin >> t;
while( t --)
{
head = tail = 0;
root = new node();
scanf( "%s" , str);
Insert( str);
build_ac_automation( root);
scanf( "%s" , str);
// Query(root);
printf( "%d \n " , Query( root));
}
return 0;
}
--------------------------------------------------------- End.
转载请注明:http://www.cnblogs.com/crazyacking/