Pagini recente » Cod sursa (job #344793) | Borderou de evaluare (job #2073085) | Borderou de evaluare (job #495320) | Cod sursa (job #155316) | Cod sursa (job #3195103)
#include <bits/stdc++.h>
using namespace std;
ifstream fin;
ofstream fout;
char a[2000005], b[2000005];
int tabel[2000005], n, m, k, i, cont=0;
vector<int> v;
int main()
{
fin.open("strmatch.in");
fin>>a>>b;
fin.close();
n=strlen(a), m=strlen(b);
i=1;
while (i<n){
if (a[i]==a[k]){
k++;
tabel[i]=k;
i++;
}
else if (k!=0){
k=tabel[k-1];
}
else {
tabel[i]=0;
i++;
}
}
i=0, k=0;
while (i<m){
if (b[i]==a[k]){
i++;
k++;
if (k==n){
cont++;
if (cont<=1000){
v.push_back(i-n);
}
k=tabel[k-1];
}
}
else if (b[i]!=a[k]){
if (k!=0)k=tabel[k-1];
else i++;
}
}
fout.open("strmatch.out");
fout<<cont<<endl;
for (i=0; i<v.size(); i++){
fout<<v[i]<<" ";
}
fout.close();
return 0;
}