KTLT2. Tần số

Tiêu đề: KTLT2. Tần số Tue May 10, 2022 3:22 pm

KTLT.2) Tần số
Nhiều hằng cơ bản là số vô tỷ và các chữ số trong hằng xuất hiện gần ngẫu nhiên. Để kiểm tra xem các chữ số trong một hằng có thể sử dụng như bộ số ngẫu nhiên hay không người ta lấy chuỗi N chữ số liên tiếp của nó và tính tần số xuất hiện của các chuỗi số S1, S2, . . ., SK (1 ≤ N ≤ 1 000 000, 1 ≤ K ≤ 1000). Chuỗi Si có độ dài không vượt quá 100.
Yêu cầu: Tính tần số xuất hiện các xâu Si, i = 1, 2, …, K.
Dữ liệu: Vào từ file văn bản FREQ.INP:
• Dòng đầu tiên chứa số nguyên K – số lượng xâu
• Dòng thứ i trong K dòng tiếp theo chứa xâu ký tự số Si,
• Xâu S0.
Kết quả: Đưa ra file văn bản FREQ.OUT K số nguyên, mỗi số trên một dòng. Số nguyên thứ i xác định số lần xuất hiện Si trong xâu S0.
Ví dụ:
FREQ.INP
3
1828
90
1234
2718281828459045235360
FREG.OUT
2
1
0

Tổng số bài gửi : 1 Join date : 03/05/2022

Code:: /*
   Loli failed to get a prize in VOI 2022, so Loli will try again in 2023,
   while struggling to solve a simple problem at 20:09 on 10.05.2022.
*/
#include <bits/stdc++.h>
using namespace std;

#pragma region Define
   #define ll long long
   // #define int long long
   #define pii pair<int, int>
   #define vi vector<int>
   #define pb push_back
   #define fr first
   #define sc second
   #define fi(x, a, b) for(int (x)=(int)a; (x)<=(int)b; ++(x))
   #define fd(x, a, b) for(int (x)=(int)a; (x)>=(int)b; --(x))
   #define bit(x, n) ((x)&(1<<(n)))
   const int oo=1e9+7;
   const ll lloo=1e18+7;
#pragma endregion

#define task "FREQ"
#define nmax 1000007
const int mod = (int)1e9 + 7;
const int base=101;
const ll mm = 1LL*mod*mod;

int n, m, k;
string s;
ll h[nmax], f[nmax];
int hashS[nmax];
set<int> len;
map<int, int> mp;

int getHash(int u, int v) {
   return (f[v] - f[u-1] * h[v-u+1] + mm) % mod;
}

void loli() {
   cin >> k;
   fi(i,1,k) {
   cin >> s;
   n = s.size();
   len.insert(n);
   fi(j,0,n-1) hashS[i] = ((hashS[i]*base) + s[j]) % mod;
   }
   cin >> s;
   m = s.size();
   s = " " + s;
   f[0] = 0;
   fi(i,1,m) f[i] = ((f[i-1]*base) + s[i]) % mod;
   h[0] = 1;
   fi(i,1,m) h[i] = (h[i-1]*base)%mod;
   for(int j: len) {
   fi(i,1,m-j+1) ++mp[getHash(i, i+j-1)];
   }
   fi(i,1,k) cout << mp[hashS[i]] << '\n';
}

signed main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int test = 1;
   freopen(task".INP","r",stdin);
   freopen(task".OUT","w",stdout);
   // cin >> test;
   while(test--) loli();
   return 0;
}

Tổng số bài gửi : 19 Join date : 09/05/2022

Bài này code Pascal ạ

Code:: uses math,crt;
var s:array[-5..1007] of string;
   st:string;
   i,n,dem:longint;
procedure kt(u:string);
var str:string;
begin
   str:=st; dem:=0;
   while (pos(u,str)<>0) do
   begin
   inc(dem);
   delete(str,pos(u,str),length(u));
   end;
end;
begin
   assign(input,'freq.inp'); reset(input);
   assign(output,'freq.out'); rewrite(output);
   readln(n);
   for i:=1 to n do readln(s[i]);
   read(st);
   for i:=1 to n do
   begin
   kt(s[i]);
   writeln(dem);
   end;
   close(input);
   close(output);
end.