Cod sursa(job #1923702)
Utilizator | Data | 11 martie 2017 21:59:46 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include<bits/stdc++.h>
#define N 2000020
using namespace std;
string a, b;
int p[N], rez[N], sol;
int main(){
int n, m;
ifstream f("file.in");
ofstream g("file.out");
f>>b>>a;
n=a.length();
m=b.length();
int i=1;
int j=0;
for(; i<m;i++){
while(j>0 && b[i]!=b[j]) j=p[j-1];
if(b[i]==b[j]) j++;
p[i]=j;
}
j=0;
for(i=0;i<n;i++){
while(b[j]!=a[i] && j>0) j=p[j-1];
if(b[j]==a[i]) j++;
if(j==m){
sol++;
rez[sol]=i-j+1;
}
}
g<<sol<<endl;
sol=min(sol, 1000);
for(i=1;i<=sol;i++) g<<rez[i]<<' ';
return 0;
}