Pagini recente » Cod sursa (job #1871879) | Cod sursa (job #151782) | Cod sursa (job #2330589) | Cod sursa (job #1762067) | Cod sursa (job #2963651)
#include <fstream>
#include <climits>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char tx[2000005];
char pat[2000005];
vector <int> sol;
int hv_txt(int p1,int p2)
{
long long s=0;
for(int i=p1;i<=p2;i++)
{
s+=tx[i];
}
return s%INT_MAX;
}
int hv_pat(int p1,int p2)
{
long long s=0;
for(int i=p1;i<=p2;i++)
{
s+=pat[i];
}
return s%INT_MAX;
}
int main()
{
fin>>pat;
fin>>tx;
int tx_last = strlen(tx)-1;
int pat_last = strlen(pat)-1;
int patvalue = hv_pat(0,pat_last);
int txtvalue = hv_txt(0,pat_last-1);
for(int last = pat_last;last<=tx_last;last++)
{
txtvalue+=hv_txt(last,last);
if(txtvalue==patvalue && tx[last]==pat[pat_last])
{
bool ok = true;
for(int i=0;i<=pat_last;i++)
{
if(pat[i]!=tx[last-pat_last+i])
{
ok=false;
break;
}
}
if(ok)
{
sol.push_back(last-pat_last);
}
}
txtvalue-=hv_txt(last-pat_last,last-pat_last);
}
fout<<sol.size()<<'\n';
for(int i=0;i<min(1000,int(sol.size()));i++)
{
fout<<sol[i]<<' ';
}
}