Pagini recente » Cod sursa (job #1527289) | Cod sursa (job #3251672) | Cod sursa (job #245476) | Cod sursa (job #2846348) | Cod sursa (job #2951211)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int OUT = 1000;
const int LIM = 2e6;
string a, b;
int asize, bsize;
int lung, pref[LIM + 5];
int out, sol[OUT + 5];
int main (){
ios_base::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
///il caut pe a in b
fin>>a>>b;
a = " " + a, asize = (int)a.size() - 1;
b = " " + b, bsize = (int)b.size() - 1;
lung = 0;
pref[1] = 0;
for(int i=2; i<=asize; i++){
while(lung > 0 && a[lung+1] != a[i])
lung = pref[lung];
if(a[lung+1] == a[i])
lung++;
pref[i] = lung;
}
lung = 0;
for(int i=1; i<=bsize; i++){
while(lung > 0 && a[lung+1] != b[i])
lung = pref[lung];
if(a[lung+1] == b[i])
lung++;
if(lung == asize){
out++;
if(out <= OUT)
sol[out] = i - lung;
}
}
fout<<out<<"\n";
for(int i=1; i<=min(out, OUT); i++)
fout<<sol[i]<<" ";
return 0;
}