Cod sursa(job #2471542)
| Utilizator | Data | 11 octombrie 2019 08:52:33 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.73 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2e6+4;
string a,b;
long long sol,lps[NMAX],sz,poz[1004],n;
void build(){
int k;
for(int i=1;i<a.size();++i){
k=lps[i-1];
while(a[k]!=a[i]){
if(!k){
k=-1;
break;
}
k=lps[k-1];
}
lps[i]=k+1;
if(lps[i] == sz){
++sol;
if(n<1000)
poz[n++]=i-sz*2;
}
}
}
int main(){
fin>>a>>b;
sz=a.size();
a=a+"#"+b;
build();
fout<<sol<<'\n';
for(int i=0;i<n;++i)
fout<<poz[i]<<' ';
return 0;
}
///KMP
