Pagini recente » Cod sursa (job #1561028) | Cod sursa (job #292338) | Cod sursa (job #1644189) | Cod sursa (job #2949449) | Cod sursa (job #866630)
Cod sursa(job #866630)
// Include
#include <fstream>
#include <cstring>
using namespace std;
// Constante
const int sz = (int)2e6+1;
const int mod1 = 20007;
const int mod2 = 20021;
const int P = 73;
// Variabile
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char sub[sz], str[sz];
int subLen, strLen;
int hash1, hash2;
int current1, current2;
int P1=1, P2=1;
int answer;
int answers[1001];
// Main
int main()
{
in >> sub >> str;
subLen = strlen(sub);
strLen = strlen(str);
hash1 = hash2 = (int)sub[0];
current1 = current2 = (int)str[0];
for(int i=1 ; i<subLen ; ++i)
{
hash1 = (hash1 * P + sub[i]) % mod1;
hash2 = (hash2 * P + sub[i]) % mod2;
current1 = (current1 * P + str[i]) % mod1;
current2 = (current2 * P + str[i]) % mod2;
P1 = (P1*P) % mod1;
P2 = (P2*P) % mod2;
}
if(hash1 == current1 && hash2 == current2)
{
if(++answer <= 1000)
answers[answer] = 0;
}
for(int i=subLen ; i<=strLen ; ++i)
{
current1 = ((current1 - str[i-subLen]*P1) % mod1) + mod1;
current1 = (current1 * P + str[i]) % mod1;
current2 = ((current2 - str[i-subLen]*P2) % mod2) + mod2;
current2 = (current2 * P + str[i]) % mod2;
if(hash1 == current1 && hash2 == current2)
if(++answer <= 1000)
answers[answer] = i-subLen + 1;
}
int limit = min(answer, 1000);
out << answer << '\n';
for(int i=1 ; i<=limit ; ++i)
out << answers[i] << ' ';
out << '\n';
in.close();
out.close();
return 0;
}