本文共 5456 字，大约阅读时间需要 18 分钟。
lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题
水题
就是用来试试字符串算法的
tri树
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define For(i, x, y) for(int i=x; i<=y; i++) #define _For(i, x, y) for(int i=x; i>=y; i--)#define Mem(f, x) memset(f, x, sizeof(f)) #define Sca(x) scanf("%d", &x)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i = 0; i <= N ; i ++) u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second using namespace std;typedef vector VI;const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; inline int read(){ int now=0;register char c=getchar(); for(;!isdigit(c);c=getchar()); for(;isdigit(c);now=now*10+c-'0',c=getchar()); return now;}int N,M;string s;char a[210];int ans,tot;int tree[maxn][30];int flag[maxn];void insert(char *str){ int l = strlen(str); int root = 0; for(int i = 0 ; i < l; i ++){ int id = str[i] - 'a'; if(!tree[root][id]){ tree[root][id] = ++tot; } root = tree[root][id]; } if(!flag[root]){ ans += flag[root] = 1; }}int main(){ while(getline(cin,s) && s[0] != '#'){ Mem(tree,0); Mem(flag,0); tot = 0; ans = 0; stringstream ss(s); while(ss >> a){ insert(a); } Pri(ans); } return 0;}
map/set
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define For(i, x, y) for(int i=x; i<=y; i++) #define _For(i, x, y) for(int i=x; i>=y; i--)#define Mem(f, x) memset(f, x, sizeof(f)) #define Sca(x) scanf("%d", &x)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i = 0; i <= N ; i ++) u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second using namespace std;typedef vector VI;const double eps = 1e-9;const int maxn = 1e5 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; inline int read(){ int now=0;register char c=getchar(); for(;!isdigit(c);c=getchar()); for(;isdigit(c);now=now*10+c-'0',c=getchar()); return now;}int N,M;string a,s;int ans = 0;map P;int main(){ while(getline(cin,s) && s[0] != '#'){ P.clear(); ans = 0; stringstream ss(s); while(ss >> a){ if(!P[a]){ ans++; P[a] = 1; } } Pri(ans); } return 0;}
Hash
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;const int MAXBUF=10000;char buf[MAXBUF],*ps=buf,*pe=buf+1;inline bool isdigit(const char& n) { return (n>='0'&&n<='9');}inline void rnext(){ if(++ps==pe)pe=(ps=buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);}template inline bool in(T &ans){#ifdef VSCodeans=0;T f=1;register char c;do{c=getchar();if ('-'==c)f=-1;}while(!isdigit(c)&&c!=EOF);if(c==EOF)return false;do{ans=(ans<<1)+(ans<<3)+c-48;c=getchar();}while(isdigit(c)&&c!=EOF);ans*=f;return true;#endif#ifndef VSCode ans =0;T f=1;if(ps==pe)return false;do{rnext();if('-'==*ps)f=-1;} while(!isdigit(*ps)&&ps!=pe);if(ps==pe)return false;do{ans=(ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps)&&ps!=pe);ans*=f;return true;#endif}const int MAXOUT=10000; //*(int(*)[10])pchar bufout[MAXOUT], outtmp[50],*pout = bufout, *pend = bufout+MAXOUT;inline void write(){fwrite(bufout,sizeof(char),pout-bufout,stdout);pout = bufout;}inline void out_char(char c){*(pout++)=c;if(pout==pend)write();}inline void out_str(char *s){ while(*s){*(pout++)=*(s++);if(pout==pend)write();}}template inline void out_int(T x) { if(!x){out_char('0');return;}if(x<0)x=-x,out_char('-');int len=0;while(x){outtmp[len++]=x%10+48;x/=10;}outtmp[len]=0;for(int i=0,j=len-1;i inline int in(T& value, T2&... value2) { in(value); return in(value2...); }#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second #define Vec Pointtypedef vector VI;const double eps = 1e-9;const int maxn = 1e6 + 10;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,tmp,K; char str[maxn];string s;vector P;ULL Hash(char *p){ ULL h = 0; ULL g; for (; *p; p++) { h = (h << 4) + *p; g = h & 0xF0000000; if (g) { h ^= (g >> 24); h ^= g; } } return h;}int main(){ while(getline(cin,s) && s[0] != '#'){ stringstream ss(s); P.clear(); while(ss >> str) P.pb(Hash(str)); sort(P.begin(),P.end()); P.erase(unique(P.begin(),P.end()),P.end()); Pri(P.size()); } #ifdef VSCode write(); system("pause"); #endif return 0;}
转载于:https://www.cnblogs.com/Hugh-Locke/p/9499707.html