fork(25) download
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <cstdlib>
  6.  
  7. using namespace std;
  8.  
  9. const int MN = 1000111;
  10.  
  11. char s[MN], t[MN];
  12. int next[MN];
  13.  
  14. int main() {
  15. scanf("%s\n", &t[1]);
  16. scanf("%s\n", &s[1]);
  17.  
  18. int j;
  19. j = next[1] = 0;
  20. for(int i = 2; s[i]; ++i) {
  21. while (j > 0 && s[j+1] != s[i]) j = next[j];
  22. if (s[j+1] == s[i]) ++j;
  23. next[i] = j;
  24. }
  25.  
  26. j = 0;
  27. for(int i = 1; t[i]; ++i) {
  28. while (j > 0 && s[j+1] != t[i]) j = next[j];
  29. if (s[j+1] == t[i]) ++j;
  30.  
  31. if (s[j+1] == 0) { // Het xau s
  32. printf("%d ", i - j + 1);
  33. j = next[j];
  34. }
  35. }
  36. puts("");
  37. return 0;
  38. }
  39.  
Success #stdin #stdout 0s 8760KB
stdin
Standard input is empty
stdout