Pagini recente » Cod sursa (job #1719713) | Cod sursa (job #2181235)
#include<bits/stdc++.h>
using namespace std;
string a, b;
const int N=2000020;
int p[N];
int main(){
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
int i=1, j=0;
int n=a.size(), m=b.size();
for(;i<n;i++){
while(j>0 && a[i]!=a[j])j=p[j-1];
if(a[i]==a[j])j++;
p[i]=j;
}
j=0;
int k=0;
vector <int> s;
for(i=0;i<m;i++){
while(j>0 && b[i]!=a[j])j=p[j-1];
if(b[i]==a[j])j++;
if(j==n){
k++;
s.push_back(i-j+1);
}
}
g<<k<<'\n';
for(i=0;i<k;i++)g<<s[i]<<' ';
}