문자열 문제 템 플 릿 장기 업데이트
7468 단어 접미사 배열
#include
#include
#include
#include
using namespace std;
const int maxn = 1e5+5;
int t1[maxn], t2[maxn], c[maxn]; //c
//
int ra[maxn], height[maxn]; //rank ,
int sa[maxn]; //suffix array
char str[maxn];
int n;
bool cmp(int *r, int a, int b, int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(char str[], int sa[], int ra[], int height[], int n, int m)
{
n++;
int i, j, p, *x = t1, *y = t2;
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[i]=str[i]]++;
for(i = 1; i < m; i++) c[i] += c[i-1];
for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
for(j = 1; j <= n; j<<=1)
{
p = 0;
for(i = n-j; i < n; i++) y[p++] = i;
for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i]-j;
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 1; i < m; i++) c[i] += c[i-1];
for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1; x[sa[0]] = 0;
for(i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
if(p >= n) break;
m = p;
}
int k = 0;
n--;
for(i = 0; i <= n; i++) ra[sa[i]] = i;
for(i = 0; i < n; i++)
{
if(k) k--;
j = sa[ra[i]-1];
while(str[i+k]==str[j+k]) k++;
height[ra[i]] = k;
}
}
int main(void)
{
while(~scanf(" %s", str))
{
n = strlen(str);
da(str, sa, ra, height, n, maxn);
for(int i = 1; i <= n; i++)
printf("%d%c", sa[i]+1, i==n ? '
' : ' ');
for(int i = 2; i <= n; i++)
printf("%d%c", height[i], i==n ? '
' : ' ');
}
return 0;
} 사전 트 리
(기본 동작 은 하나의 문자열 을 접두사 로 하 는 단어의 수 를 삽입 하고 조회 하 는 것 입 니 다)
포인터 (동적 템 플 릿)
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
struct Trie{
Trie *next[26];//next ， ， 26 ，
// ， 52， ， 62 ， 。
int num;
//num ， 。
Trie()
{
int i;
for(int i=0;i<26;i++)
next[i]=NULL;
num=0;
}
}root;
void insert(char s[])// s
{
Trie *p=&root;
int i;
for(int i=0;s[i];i++)// s
{
if(p->next[s[i]-'a']==NULL) //
p->next[s[i]-'a']=new Trie;
p=p->next[s[i]-'a'];
p->num++;
}
}
int find(char s[])// s
{
Trie *p=&root;
int i;
for(int i=0;s[i];i++)//
{
if(p->next[s[i]-'a']==NULL)
return 0;
p=p->next[s[i]-'a'];
}
return p->num;
}
int main(){
char s[20];
while(gets(s))
{
if(strlen(s)==0||s[0]==NULL)
break;
insert(s);
}
while(~scanf("%s",s))
{
printf("%d
",find(s));
}
return 0;
}
정적 템 플 릿
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=1e6+10;
int trie[maxn][26];
// ,
int num[maxn]={0};
// ,
int pos=1;
void insert(char s[])// s
{
int c=0;
for(int i=0;s[i];i++)
{
int n=s[i]-'a';
if(trie[c][n]==0)//
trie[c][n]=pos++;
c=trie[c][n];
num[c]++;
}
}
int find(char s[])//
{
int c=0;
for(int i=0;s[i];i++)
{
int n=s[i]-'a';
if(trie[c][n]==0)
return 0;
c=trie[c][n];
}
return num[c];
}
int main(){
char s[20];
while(gets(s))
{
if(strlen(s)==0||s[0]==NULL)
break;
insert(s);
}
while(~scanf("%s",s))
{
printf("%d
",find(s));
}
return 0;
}
01trie
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int maxn=6e6+10;
const int N=3e5+10;
int trie[maxn][5];
int num[maxn];
int vis[2*N];
int pos=1;
int now;
char str[25];
void insert(char s[],int val)
{
int c=0;
int len = strlen(s);
for(int i=0;i < len;i++)
{
int bt=s[i]-'0';
if(trie[c][bt]==0)
{
num[pos] = 0;
memset(trie[pos],0,sizeof trie[pos]);
trie[c][bt]=pos++;
}
c=trie[c][bt];
}
num[c] = val;
return ;
}
int find(char s[])
{
int c=0;
int len = strlen(s);
for(int i=0;i < len;i++)
{
int bt=s[i]-'0';
if(trie[c][bt])
c=trie[c][bt];
else
c=trie[c][1-bt];
}
return num[c];
}
void change(int i)
{
str[21]='\0';
int tmp = i;
for(int j = 20;j >= 0;j--)
{
if(tmp)
{
str[j] = tmp%2 +'0';
tmp /= 2;
}
else
str[j] = '0';
}
}
int main(){
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i++)
{
int a;
scanf("%d",&a);
if(vis[a]==0)
vis[a] = 1;
}
for(int i = 0;i <= 600000 ;i++)
{
if(vis[i] == 0)
{
change(i);
insert(str,i);
}
}
now = 0;
while(m--)
{
int x;
scanf("%d",&x);
now ^= x;
x = now;
change(x);
printf("%d
",find(str)^now);
}
return 0;
}
문자열 해시
#include
using namespace std;
typedef unsigned long long ull;
const ull base=123;
const int maxn=4e5+10;
const int hashh= 1e6+10;
char s[511][511];
ull num[511*511],f[511][511];
int n,m;
struct hashmap
{
ull a[maxn];
int head[hashh];
int nxt[maxn];
int siz;
void init()
{
memset(head,-1,sizeof head);
siz = 0;
}
bool find(ull val)
{
int tmp = (val % hashh + hashh) % hashh;
for(int i = head[tmp];i!=-1;i = nxt[i])
{
if(val == a[i]) return true;
}
return false;
}
void add(ull val)
{
int tmp = (val % hashh + hashh) % hashh;
if(find(val)) return ;
a[siz] = val;
nxt[siz] = head[tmp];// next -1;
head[tmp] = siz++;
}
}Hash;
void init()
{
memset(f,0,sizeof f);
num[0]=1;
int cnt = 0;
for(int i = 1; i <= n;i++)
for(int j = 1;j <= m;j++)
{
cnt++;
num[cnt] = num[cnt-1]*base;
f[i][j] = f[i-1][j] + f[i][j-1] -f[i-1][j-1] + (s[i][j]-'0')*num[cnt];
}
return ;
}
bool check(int x)
{
Hash.init();
for(int i = x;i <= n;i++)
for(int j = x;j <= m;j++)
{
ull tmp = f[i][j] - f[i][j - x] - f[i - x][j] + f[i - x][j - x];
tmp = tmp * num[(n - i) * m + m - j];
if(Hash.find(tmp) == true)
return true;
Hash.add(tmp);
}
return false;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
for(int i = 1;i <= n;i++) scanf("%s",s[i]+1);
init();
int l = 1,r=min(n,m),mid,ans = -1;
while(l<=r)
{
mid = (l + r) >> 1;
if(check(mid))
l = mid + 1,ans = mid;
else
r = mid - 1;
}
printf("%d
",ans);
}
return 0;
}
좋은 웹페이지 즐겨찾기
