Pagini recente » Cod sursa (job #1237592) | Cod sursa (job #2044229) | Cod sursa (job #2097044) | Cod sursa (job #1034482) | Cod sursa (job #1681630)
///Rabin-Karp
/*#include <fstream>
#include <string>
#define NMAX 2000005
#define BASE 101
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string A, B;
int hash1_A, hash2_A, hash1_B, hash2_B, reh_base1, reh_base2, ans_nr;
bool match[NMAX];
int main() {
cin >> A;
cin >> B;
if(A.size() > B.size()) {
cout << 0 << '\n';
return 0;
}
reh_base1 = reh_base2 = 1;
for(int i = 0; i < (int) A.size(); ++i) {
hash1_A = (hash1_A * BASE + A[i]) % MOD1;
hash2_A = (hash2_A * BASE + A[i]) % MOD2;
if(i) {
reh_base1 = (reh_base1 * BASE) % MOD1;
reh_base2 = (reh_base2 * BASE) % MOD2;
}
}
for(int i = 0; i < (int) A.size(); ++i) {
hash1_B = (hash1_B * BASE + B[i]) % MOD1;
hash2_B = (hash2_B * BASE + B[i]) % MOD2;
}
if(hash1_A == hash1_B and hash2_A == hash2_B) {
match[0] = true;
++ans_nr;
}
for(int i = (int) A.size(); i < (int) B.size(); ++i) {
hash1_B = hash1_B - (B[i - A.size()] * reh_base1) % MOD1 + MOD1;
hash1_B = (hash1_B * BASE + B[i]) % MOD1;
hash2_B = hash2_B - (B[i - A.size()] * reh_base2) % MOD2 + MOD2;
hash2_B = (hash2_B * BASE + B[i]) % MOD2;
if(hash1_A == hash1_B and hash2_A == hash2_B) {
match[i - A.size() + 1] = true;
++ans_nr;
}
}
cout << ans_nr << '\n';
ans_nr = min(ans_nr, 1000);
for(int i = 0; i < (int) B.size() and ans_nr; ++i) {
if(!match[i]) {
continue;
}
--ans_nr;
cout << i << ' ';
}
cout << '\n';
return 0;
}
*/
///KMP
/*#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int MaxLng = 2000005;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector <int> ans;
string A, B;
int pref[MaxLng];
int k, ans_sz;
int main() {
string str;
cin >> str;
A.push_back('0');
A += str;
cin >> str;
B.push_back('0');
B += str;
for(int i = 2; i <= (int) A.size() - 1; ++i) {
k = pref[i - 1];
while(k and A[k + 1] != A[i]) {
k = pref[k];
}
if(A[k + 1] == A[i]) {
++k;
}
pref[i] = k;
}
k = 0;
for(int i = 1; i <= (int) B.size() - 1; ++i) {
while(k and A[k + 1] != B[i]) {
k = pref[k];
}
if(A[k + 1] == B[i]) {
++k;
}
if(k == (int) A.size() - 1) {
++ans_sz;
if(ans.size() < 1000) {
ans.push_back(i - (A.size() - 1));
}
}
}
cout << ans_sz << '\n';
for(auto it: ans) {
cout << it << ' ';
}
return 0;
}
*/
///Z Algorithm
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
const int MaxLng = 2000005;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
vector <int> ans;
string A, B;
int Z[MaxLng], Z_sr[MaxLng];
int szA, szB, last, ans_nr;
int main() {
string str;
cin >> str;
A.push_back('0');
A += str;
szA = A.size() - 1;
cin >> str;
B.push_back('0');
B += str;
szB = B.size() - 1;
last = 0;
for(int i = 2; i <= szA; ++i) {
if(last + Z_sr[last] > i) {
Z_sr[i] = min(Z_sr[i - last + 1], last + Z_sr[last] - i);
}
while(i + Z_sr[i] <= szA and A[i + Z_sr[i]] == A[Z_sr[i] + 1]) {
++Z_sr[i];
}
if(i + Z_sr[i] > last + Z_sr[last]) {
last = i + Z_sr[i];
}
}
last = 0;
for(int i = 1; i <= szB; ++i) {
if(last + Z[last] > i) {
Z[i] = min(Z_sr[i - last + 1], last + Z[last] - i); ///i - last + 1 = correspondent of i in pattern; last + Z[last] - i = distance from i to end of generated path
}
while(Z[i] + 1 <= szA and i + Z[i] <= szB and A[Z[i] + 1] == B[i + Z[i]]) {
++Z[i];
}
if(i + Z[i] > last + Z[last]) {
last = i;
}
if(Z[i] == szA) {
++ans_nr;
if(ans_nr <= 1000) {
ans.push_back(i);
}
}
}
cout << ans_nr << '\n';
for(auto it: ans) {
cout << it - 1 << ' ';
}
return 0;
}