Pagini recente » Cod sursa (job #226356) | Cod sursa (job #562401) | Cod sursa (job #389259) | Cod sursa (job #1252390) | Cod sursa (job #1398261)
#include <fstream>
#include <cstring>
#include <iostream>
#define mod1 666013
#define mod2 100019
using namespace std;
string s, p;
int lenP, lenS, P1, P2, num1, num2, aux1, aux2, rez;
int S[1005];
int main()
{
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
getline(fi, p);
getline(fi, s);
lenP = int( p.size() );
lenS = int( s.size() );
if (lenP > lenS)
{
fo << 0 << "\n";
return 0;
}
num1 = num2 = 0;
P1 = P2 = 1;
for (int i = 0; i < lenP; i++)
{
num1 = (num1 * 26 + p[i]) % mod1;
num2 = (num2 * 27 + p[i]) % mod2;
if (i > 0)
{
P1 = (P1 * 26) % mod1;
P2 = (P2 * 27) % mod2;
}
}
aux1 = aux2 = 0;
for (int i = 0; i < lenP; i++)
{
aux1 = (aux1 * 26 + s[i]) % mod1;
aux2 = (aux2 * 27 + s[i]) % mod2;
}
if (aux1 == num1 && aux2 == num2)
{
rez++;
S[rez] = 0;
}
for (int i = lenP; i < lenS; i++)
{
aux1 = ((((aux1 - (P1 * s[i - lenP])) % mod1) + mod1) * 26 + s[i]) % mod1;
aux2 = ((((aux2 - (P2 * s[i - lenP])) % mod2) + mod2) * 27 + s[i]) % mod2;
if (aux1 == num1 && aux2 == num2)
{
rez++;
if (rez <= 1000)
S[rez] = i - lenP + 1;
}
}
fo << rez << "\n";
for (int i = 1; i <= min(1000, rez); i++)
fo << S[i] << " ";
fo << "\n";
fi.close();
fo.close();
return 0;
}