Pagini recente » Cod sursa (job #945922) | Cod sursa (job #3125889) | Cod sursa (job #2637377) | Cod sursa (job #1090847) | Cod sursa (job #1867901)
#include <iostream>
//das karp
#include <vector>
#include <algorithm>
#include <cmath>
#include <algorithm>
#include <string>
#include <fstream>
#define ll long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int prim = 3;
string a,b;
ll geth(int n,int p,ll inh){
inh -= b[n]-'A'+1;
inh/=prim;
inh+= (b[p]-'A'+1)*pow(prim,p-n-1);
return inh;
}
int mycheck(int aux){
int rez = aux;
for(int i=0;i<a.size();i++,aux++){
if(a[i] != b[aux])
return -1;
}
return rez;
}
int main()
{
vector<int>rez;
int ih=0,sh=0;
fin>>a>>b;
for(int i=0;i<a.size();i++){
sh+=(a[i]-'A'+1)*pow(prim,i);
ih+=(b[i]-'A'+1)*pow(prim,i);
}
int aux=0;
for(int i=a.size()-1;i<b.size();i++){
if(sh == ih){
if(mycheck(aux)!=-1){
rez.push_back(aux);
}
aux++;
}
else {
ih = geth(aux,i+1,ih);
aux++;
}
}
fout<<rez.size()<<'\n';
for(int i=0;i<rez.size();i++)
if(i<=999)
fout<<rez[i]<<' ';
else
break;
return 0;
}