Pagini recente » Photo | Cod sursa (job #2874226) | Cod sursa (job #2613469) | Cod sursa (job #2328725) | Cod sursa (job #1831520)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string pattern,omega;
char x;
int hashOmega[2000005];
int i;
vector<int> aparitii;
int hashString(string &wow, int start, int stop)
{
const int PRIME = 3079;
int ans=1;
for(int j=start;j<=stop;j+=1)
ans=(ans*(int)wow[j])%PRIME;
return (int)ans;
}
int main()
{
fin>>pattern;
while(fin>>x)
{
omega+=x;
if(omega.size()<pattern.size()) continue;
hashOmega[i++]=hashString(omega, omega.size()-pattern.size(), omega.size()-1);
}
if(pattern.size()>omega.size())
{
fout<<0;
return 0;
}
int hashPattern = hashString(pattern, 0, pattern.size()-1);
for(int j=0;j<i;j+=1)
{
if(hashPattern==hashOmega[j])
{
bool ok=1;
for(int y=j,t=0;y<j+pattern.size()&&ok;y+=1,t+=1) if(pattern[t]!=omega[y])ok=0;
if(ok) aparitii.push_back(j);
}
}
fout<<aparitii.size()<<'\n';
for(auto j:aparitii) fout<<j<<' ';
return 0;
}