Cod sursa(job #2181239)
| Utilizator | Data | 21 martie 2018 15:41:38 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.54 kb |
#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);
if(k==1000)break;
}
}
g<<k<<'\n';
for(i=0;i<k;i++)g<<s[i]<<' ';
}
