Pagini recente » Cod sursa (job #1382156) | Cod sursa (job #2324370) | Cod sursa (job #859761) | Cod sursa (job #2847151) | Cod sursa (job #1276236)
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define N 2000002
#define P 191
char substr[N],str[N];
int main ()
{
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
fscanf(fin,"%s %s", substr, str);
long long int hash_substr = 0LL;
int len = strlen(substr);
long long int P_len = 1LL;
for(int i=0;i<len; i++)
{
hash_substr = (hash_substr * P + substr[i]);
P_len = (P_len * P);
}
long long int hash_str=0;
int i;
for(i=0;i<len;i++)
{
hash_str = (hash_str*P + str[i]);
}
std::vector<int> v;
for(;i<=strlen(str);i++)
{
if(hash_str==hash_substr)
{
v.push_back(i-len);
/*
int flag = true;
for(int j=0;j<len;j++)
{
if(substr[j] != str[i+j-len])
{
flag=false;
}
}
if(flag)
{
v.push_back(i-len);
}*/
}
hash_str = (hash_str * P + str[i] - P_len*str[i - len]);
}
fprintf(fout, "%d\n", v.size());
for(auto& e: v)
{
fprintf(fout, "%d ", e);
}
return 0;
}