Mai intai trebuie sa te autentifici.
Cod sursa(job #627185)
| Utilizator | Data | 29 octombrie 2011 11:54:01 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 80 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.73 kb |
#include <fstream>
#include <string>
using namespace std;
string s,x;
int pr[100001],k,prv[100001];
int n,i,j,pot,xl,sl;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>x>>s;
for (i=s.length(); i>=1; i--)
s[i]=s[i-1];
for (i=x.length(); i>=1; i--)
x[i]=x[i-1];
xl=x.length();
sl=s.length();
for (i=2; i<=xl; i++) {
k=pr[i-1];
while(k&&x[k+1]!=x[i])
k=pr[k];
if (x[k+1]==x[i])
k++;
pr[i]=k;
}
k=0;
for (i=1;i<=sl;i++) {
while(k&&x[k+1]!=s[i])
k=pr[k];
if (x[k+1]==s[i])
k++;
if (k==xl) {
pot++;
if (pot<=1000)
prv[pot]=i-xl;
}
}
g<<pot<<'\n';
for (i=1; i<=min(pot,1000); i++)
g<<prv[i]<<' ';
g.close();
return 0;
}
