Mai intai trebuie sa te autentifici.
Cod sursa(job #2353470)
| Utilizator | Data | 24 februarie 2019 12:28:48 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 32 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.34 kb |
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
string a, b;
int lp[2000005], la, lb;
vector <int> sol;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
getline(cin,a);
getline(cin,b);
la=a.length();
lb=b.length();
int k=0;
for(int i=1 ; i<la; ++i){
if(a[k]==a[i])
lp[i] = ++k;
else{
--k;
//k=lp[k];
while(k>=0){
k=lp[k];
if(a[k]==a[i]){
lp[i]=++k;
break;
}
--k;
}
if(k<0)
lp[i]=0, k=0;
}
}
k==0;
for(int i=0;i<lb;++i){
if(k==la){
sol.push_back(i-la);
k=lp[k-1];
}
if(a[k]==b[i])
++k;
else{
k--;
while(k>=0){
k=lp[k];
if(a[k]==b[i]){
++k;
break;
}
--k;
}
if(k<0)
k=0;
}
}
if(k==la){
sol.push_back(lb-la);
}
/*
for(int i=0;i<la;++i)
cout<<lp[i]<<" ";
*/
cout<<sol.size()<<"\n";
for(int i : sol)
cout<<i<<" ";
return 0;
}
