Nu aveti permisiuni pentru a descarca fisierul grader_test6.ok
Cod sursa(job #2352338)
| Utilizator | Data | 23 februarie 2019 11:20:48 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.7 kb |
#include <bits/stdc++.h>
#define MAXN 2000010
using namespace std;
string A,B;
int Pa[MAXN],P[MAXN];
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>A>>B;
int k = 0;
//cout<<0;
for (int i = 1; i < A.size(); i++) {
while (A[k] != A[i] && k)
k = k - 1;
if (A[k] == A[i])
k++;
Pa[i] = k;
// cout<<Pa[i];
}
int j=0,i=0,l=0;
while(i<B.size()){
if(A[j]==B[i]){
i++;
j++;
}
if(j==A.size()){
P[l++]=i-j;
j=Pa[j-1];
}else if(i<B.size() && A[j]!=B[i]){
if(j!=0)j=Pa[j-1];
else i++;
}
}
cout<<l<<'\n';
l=min(l,1000);
for(int i=0;i<l;i++)cout<<P[i]<<' ';
}
