Pagini recente » Cod sursa (job #114777) | Cod sursa (job #854102) | Cod sursa (job #2123735) | Cod sursa (job #2699786) | Cod sursa (job #2339607)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
char s[2000010];
char t[2000010];
int sol[1002];
int p[2000010];
int n, m, L, aparitii = 0, i;
int main()
{
fin>>s+1;
fin>>t+1;
n = strlen(s+1);
m = strlen(t+1);
/// calculez p[i] = lungimea maxima a unei secvente din s care se termina pe pozitia i in s si care totodata
/// este la inceputul lui s
p[1] = 0;
L = 0;
for (i=2;i<=n;i++) {
/// calculez p[i]
while (L!= 0 && s[i] != s[L+1])
L = p[L];
if (s[i] == s[L+1])
L++;
p[i] = L;
}
L = 0;
for (i=1;i<=m;i++) {
/// voi testa potrivire a lui s in t care SE TERMINA la pozitia i
/// semnificatia lui L la pasul i = lungimea maxima a unui sifix din t termint la pozitia i
/// care totodata este prefix de lungime L in s
while (L!=0 && t[i] != s[L+1])
L = p[L];
if(t[i] == s[L+1])
L++;
if (L == n) {
/// potrivire
aparitii++;
if (aparitii <= 1000)
sol[aparitii] = i-n;
L = p[L];/// urmatoarea potrivire se poate suprapune cu cea curenta
/// si o cautam extinzand cel mai lung prefix al intregului sir s
}
}
fout<<aparitii<<"\n";
if (aparitii > 1000)
aparitii = 1000;
for (i=1;i<=aparitii;i++)
fout<<sol[i]<<" ";
return 0;
}