#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <cstdlib> #define INF 1000000 #define ll long long using namespace std; int main() { char s[100005]; string str; int len,i,j,idx; int *failureFunc; while(scanf("%s",s)!=EOF) { len=strlen(s); str=""; for(int y=len-1;y>=0;y–) str.append(1u,s[y]); failureFunc=(int *)malloc(sizeof(int)*len); failureFunc[0]=0; i=0; j=1; while(j<len) { if(str[i]==str[j]) { i+=1; failureFunc[j]=i; j+=1; }
Category: Data Structure
644
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; struct node{ bool end; node *nxt[2]; node() { end=false; for(int i=0;i<2;i++) nxt[i]=NULL; } }*root; int main() { string str,s; int id; node *cur,*tmp; int kase=1; while(cin>>str) { bool decodable=1; root=new node(); cur=root; int i; for( i=0;i<str.size()-1;i++) { id=str[i]-'0'; if(cur->nxt[id]==NULL) { cur->nxt[id]=new node(); } cur=cur->nxt[id];
10679
KMP algo solution* */ /* #include<stdio.h> #include<string.h> #include<stdlib.h> #include <iostream> using namespace std; void computeLPSArray(char *pat, int M, int *lps); bool KMPSearch(char *pat, char *txt) { int M = strlen(pat); int N = strlen(txt); // create lps[] that will hold the longest prefix suffix values for pattern int *lps = (int *)malloc(sizeof(int)*M); int j =
10887
#include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <sstream> #define SZ 10000017 using namespace std; char b[30]; char str[3000000][25];//3000000 int parent[10000017]; int strmap[3000000]; int gethash(char s[]) { int seed=31; int v=0; for(int i=0;i<strlen(s);i++) { v= v*seed+(s[i]-'0'); } return (v&0x7FFFFFFF)%SZ; } bool insert(int position) { int _hash = gethash(str[position]); int next=parent[_hash]; while(next!=-1) { if(!strcmp(str[position],str[next])) break;
11362
#include <iostream> #include <stdio.h> #include <vector> using namespace std; struct node{ bool endofmark; node *next[11]; node() { endofmark=false; for(int i=0;i<10;i++) next[i]=NULL; } }*root; int insert(string str) { node *curr=root; int id; int created=0; for(int i=0;i<str.size();i++) { id=str[i]-'0'; if(curr->next[id]==NULL) { curr->endofmark=false; curr->next[id]=new node(); created =1; } curr=curr->next[id]; } if(created==0) curr->endofmark=false; else curr->endofmark=true; return created; } bool
12506
#include <iostream> #include <string> #include <queue> using namespace std; int res; struct node{ int cont; node *next[26]; node() { cont=0; for(int i=0;i<26;i++) next[i]=NULL; } }*root; void insert(string s) { node *tmp= root; int len=s.size(); int idx; for(int i=0;i<len;i++) { idx= s[i]-'a'; if(tmp->next[idx]==NULL) tmp->next[idx]=new node(); tmp->next[idx]->cont++; tmp = tmp->next[idx]; } } void del(node *r) { for(int
12532
/*****Binary Index tree 12532******/ #include <stdio.h> #include <iostream> #include <string> #include <string.h> #include <math.h> #define SZ 100005 #define ll long long using namespace std; int num[SZ]; int neg[SZ]; int zero[SZ]; int maxInd; void update(int *arr,int ind,int val) { while(ind<maxInd) { arr[ind]+=val; ind+=(ind & (-ind)); } } int read(int *arr,int ind) { int res =0; while(ind>0)