Pagini recente » Cod sursa (job #1449958) | Cod sursa (job #484170) | Cod sursa (job #1930850) | Cod sursa (job #1548428) | Cod sursa (job #2719155)
#include <iostream>
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;
vector<int>r;
char s[2000001], sm[2000001];
int pi[2000001];
int main() {
int m, k, i, n, ans;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(s, 2000001);
m=strlen(s);
fin.getline(sm, 2000001);
n=strlen(sm);
for(i=m;i>=1;i--) {
s[i]=s[i-1];
}
for(i=n;i>=1;i--) {
sm[i]=sm[i-1];
}
k=0;
pi[1]=0;
ans=0;
for(i=2;i<=m;i++) {
while(k>0 && s[k+1]!=s[i]) {
k=pi[k];
}
if(s[k+1]==s[i]) {
k++;
}
pi[i]=k;
}
int q=0;
for(i=1;i<=n;i++) {
while(q>0 && s[q+1]!=sm[i]) {
q=pi[q];
}
if(s[q+1]==sm[i]) {
q++;
}
if(q==m) {
if(ans<1000){
r.push_back(i-m);
}
ans++;
}
}
fout<<ans<<"\n";
for(i=0;i<r.size();i++) {
fout<<r[i]<<" ";
}
return 0;
}