Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- char s[4000005];
- long long counter, raspuns[1001];
- int z[4000005];
- void Z_Algorithm (int lungime, int n)
- {
- z[1] = 0;
- int l, r;
- l = r = 1;
- for (int i = 2; i<=n; ++i)
- {
- if (i > r)
- {
- while (z[i] + i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
- l = i;
- r = i + z[i] - 1;
- }
- else
- {
- if (i+z[i-l+1]-1 < r)
- z[i] = z[i-l+1];
- else
- {
- z[i] = r-i;
- while (z[i] + i <= n && s[z[i]+i] == s[z[i]+1]) ++z[i];
- l = i;
- r = i + z[i] - 1;
- }
- }
- if (z[i] == lungime)
- {
- ++counter;
- if (counter <= 1000)
- raspuns[counter] = i-lungime-2;
- }
- }
- }
- int main()
- {
- ifstream fin ("strmatch.in");
- ofstream fout ("strmatch.out");
- int n, i, len;
- fin >> (s+1);
- len = strlen (s+1);
- s[len+1] = '#';
- fin >> (s+len+2);
- n = strlen(s+1);
- Z_Algorithm(len, n);
- fout << counter << '\n';
- for (int i = 1; i<=counter && i <=1000; ++i)
- fout << raspuns[i] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement