Mai intai trebuie sa te autentifici.
Cod sursa(job #2277169)
| Utilizator | Data | 5 noiembrie 2018 20:51:33 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.87 kb |
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int P[2000055],i,q,nrsol,sol[2000055];
char v[2000055],t[2000055];
void kmp(int n){
P[1]=0;
for(i=2;i<=n;i++){
q=P[i-1];
while(q&&v[i]!=v[q+1])
q = P[q];
if(v[i]==v[q+1])
q++;
P[i]=q;
}
}
int main()
{
f>>v+1;
f>>t+1;
int n= strlen(t+1);
int len=strlen(v+1);
int q=0;
kmp(len);
for(i=1;i<=n;i++){
while( q && t[i] != v[q+1])
q=P[q];
if(t[i]==v[q+1])
q++;
if(q == len){
q = P[len];
nrsol ++;
sol[nrsol]=i-len;
}
}
g<<nrsol<<'\n';
for(i=1;i<=min(nrsol,1000);i++)
g<<sol[i]<<" ";
return 0;
}
